A recursive algorithm, by definition, is a method where the solution to a problem depends on solutions to smaller instances of the same problem.
Here, the problem is to convert a number to a string in a given notation.
The "stockpiling" of data the function does actually looks like this:
push(d1)
push(d2)
...
push(dn-1)
push(dn)
res+=pop(dn)
res+=pop(dn-1)
...
res+=pop(d2)
res+=pop(d1)
which is effectively:
def pushpop():
push(dx)
pushpop(dx+1...dn)
res+=pop(dx)
I.e. a step that processes a specific chunk of data encloses all the steps that process the rest of the data (with each chunk processed in the same way).
It can be argued if the function is recursive (since they tend to apply the term to subroutines in a narrower sense), but the algorithm it implements definitely is.
For you to better feel the difference, here's an iterative solution to the same problem:
def toStr(n,base):
charmap = "0123456789ABCDEF"
res=''
while n > 0:
res = charmap[n % base] + res
n = n // base
return res
As you can see, this method has much lower memory footprint as it doesn't stockpile tasks. This is the difference: an iterative algorithm performs each step using the same instance of the state by mutating it while a recursive one creates a new instance for each step, necessarily stockpiling them if the old ones are still needed.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…