Is this function recursive even if it doesn't call itself?
from pythonds.basic.stack import Stack
rStack = Stack()
def toStr(n,base):
convertString = "0123456789ABCDEF"
while n > 0:
if n < base:
rStack.push(convertString[n])
else:
rStack.push(convertString[n % base])
n = n // base
res = ""
while not rStack.isEmpty():
res = res + str(rStack.pop())
return res
print(toStr(1345,2))
I mean this tutorial and also pasted the code above. The tutorial says the function is recursive, but I don't see the recursive call anywhere, just a while loop. What am I missing?
source to share
You are correct that this particular function is not recursive. However, the context is that there was a recursive function in the previous slide, and in this they want to show how it behaves internally. Later they say:
Previous example [ie the one in question is B.] gives us some insight into how Python implements a recursive function call.
So yes, the name is misleading, it should be more like Extending a Recursive Function or Simulating the recursive behavior of a function with a stack or something like that.
We can say that in a sense this function uses a recursive approach / strategy, the problem being solved, but not recursive.
source to share
A recursive algorithm, by definition, is a technique in which the solution to a problem depends on the solutions of smaller instances of the same problem .
The problem here is converting the number to a string in the given notation.
The "accumulation" of data that the function actually performs:
push(d1) push(d2) ... push(dn-1) push(dn) res+=pop(dn) res+=pop(dn-1) ... res+=pop(d2) res+=pop(d1)
what is effective:
def pushpop():
push(dx)
pushpop(dx+1...dn)
res+=pop(dx)
those. a step that processes a certain piece of data covers all the stages of processing the rest of the data (each processed block is processed in the same way).
One could argue that the function is recursive (since they tend to apply the term to subroutines in a narrower sense), but the algorithm it implements is definitely there.
To give you a better feel for 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 a much lower memory footprint as it does not pose a problem. This is the difference: an iterative algorithm executes each step using the same state instance, changing it, while a recursive algorithm creates a new instance for each step, making sure to accumulate them if the old ones are still needed.
source to share
Because you are using a stack structure.
If you consider how a function call is made, recursion is essentially an easy way to get the compiler to manage the call stack for you.
This function does all the stack handling by hand, but it is still conceptually a recursive function, just one where the stack is handled manually, rather than letting the compiler do it.
source to share