Oct
25
How do I make a recursive function iterative?
You've probably been told that you can convert any recursive function into an iterative loop just by using an explicit stack.
Tail-recursive functions
Whenever you get an example, it's usually something that's trivial, because the function was tail-recursive, so you don't even need a stack:
def fact(n, value=1): if n<2: return 1 return fact(n-1, value*n) That maps directly to:
def fact(n): value = 1 while True: if n<2: return value n, value = n-1, value*n You can merge the while and if, at which point you realize you have a for in disguise.
Tail-recursive functions
Whenever you get an example, it's usually something that's trivial, because the function was tail-recursive, so you don't even need a stack:
def fact(n, value=1): if n<2: return 1 return fact(n-1, value*n) That maps directly to:
def fact(n): value = 1 while True: if n<2: return value n, value = n-1, value*n You can merge the while and if, at which point you realize you have a for in disguise.
