6 ms·

Removing a recursion in Python, part 1

26 points by wglb 8y ago

giiguughh 8y ago
Is this programing 101?
valesco 8y ago
Thanks, this is very interesting. I am enrolled in a CS Bsc. (night courses) and while we learned about the different techniques of recursive programming, we never learned how to convert a recursive solution into an iterative one.
- iliketosleep 8y ago
  I remember when I was at college it was the same, and it doesn't make any sense. I can't recall any instances where I've needed to convert an iterative solution into a resursive one, but there have been countless times I've done the reverse. I belive that the mindless emphasis on resursive programming in college courses has lead to poor practices, where people are using recursion to just make their code more elegant where an iterative solution wouldn't much more complicated but a lot more robust. The result? Down the track, an unforseen use cases resulting in max stack size exceeded errors, causing needless headaches.
  - saagarjha 8y ago
    > I belive that the mindless emphasis on resursive programming in college courses has lead to poor practices, where people are using recursion to just make their code more elegant Most courses, especially introductory ones, don’t have particularly good examples of when to use recursion. This doesn’t mean that there aren’t cases where recursion isn’t useful, though.
  - gh02t 8y ago
    I think the prevalence of recursion might be attributable to mathematics. A lot of mathematical analysis of algorithms is more natural to express in terms of recursion (partially because of proof by induction), so you often see algorithms stated that way. It's also worth noting that there are plenty of instances where (IMO), recursion is much more natural. For example, traversing trees recursively. I agree, though, there should definitely be more time spent teaching how to convert between the two.
- ericlippert 8y ago
  One of the reasons I wrote this article was because of exactly the problem that you mention, so I am very happy that you found it interesting! I frequently interview recent CS graduates, and ask a technical question about techniques for removing recursions; the people who do well on such questions tend to have practical experience writing compilers. A lot of these basic techniques are not covered in undergraduate courses, but they are crucial to understanding how modern programming languages work under the hood. I still have my notes from my fourth year course in continuation passing style from my undergrad days and it was very helpful to me when we started adding these concepts to C#.
ciupicri 8y ago
A more stable link would be https://ericlippert.com/2018/12/03/removing-a-recursion-in-python/ https://ericlippert.com/2018/12/03/removing-a-recursion-in-p...
crimsonalucard 8y ago
The article doesn't explain the problem of converting recursion to iteration fully. There is a lot more detail. Most recursion can be implemented using a loop and a stack. If the recursive expression is self contained in the return call, then you don't need a stack. For example: def somefunc(x): if x <= 0: return 0 return somefunc(x-1) is equal to: def somefunc(x) while x > 0: x = x - 1 return x But if the recursion isn't self contained: def somefunc(x): if x == 0: return 0 return somefunc(x-1) + 1 then the iterative version looks like this: def somefunc(x) stack = [] while x > 0: stack.append(x) x = x - 1 while len(stack) != 0: x = x + stack[-1] stack = stack[:-1] return x During Recursion your program will use an internal stack to keep track of previous context. This is called the call stack. Whether or not you use iteration or recursion for the last example you will need a stack. The last example is actually less efficient than the recursive version because you are moving the call stack to the heap. The heap is slower than the call stack but the heap essentially has no limits so you won't encounter stack overflow. In the first example of recursion you will actually benefit from conversion to iteration because you get rid of the stack all together in the iterative example. Some languages will be able to recognize this type of recursion and do an optimization step called "tail-recursion optimization" in which the compiler actually gets rid of the need for a the call stack. Python does not do this, however. The story doesn't end here, however. There are examples of recursion where you cannot create a straightforward iterative version. For example: def somefunc(x): if x <= 0: return 0 return somefunc(x-1) + somefunc(x-2) The straight forward conversion using an explicit stack looks like this: def somefunc(x) stack = [] while x > 0: stack.append(lambda: somefunc(x-2)) x = x - 1 while len(stack) != 0: x + stack[:-1]() stack = stack[:-1] return x You will note that the straightforward conversion doesn't get rid of recursion. The reason is because the previous context is basically another recursive call. You will note that the recursive version of this function actually does the same multiple recursive calls twice which leads to unnecessary repeated calculations. It is possible to optimize this repetition using something called memoization. However memoization requires and does not get rid of recursion. It is not possible to imitate this "inn-efficiency" in an iterative form. The only way to do it is to do an optimization step similar to memoization before iterating. This step, however radically changes the way you think about the problem. It literally reverses the recursion from a top down approach to a bottom up approach. Here is what the iterative form looks like: def somefunc(x): store = [None for _ in range(x)] store[0] = 0 for i in range(1, len(store)): store[i] = store[i-1] + store[i-2] if i-2 >= 0 else 0 return store[-1] This method is called "Dynamic programming using the tabular method." You will note that this version of the function still allocates storage to the heap with "store" There is still a further optimization step you can do here as well. This optimization is basically noticing that you don't need to memorize the entire store in the algorithm. You only need the previous two values. def somefunc(x): store_i_minus_1 = 0 store_i_minus_2 = 0 for i in range(1, len(store)): result = store_i_minus_1 + store_i_minus_2 store_i_minus_1, store_i_minus_2 = result, store_i_minus_1 return result You will note that the the new example has no allocation to the heap and is the full efficient iterative version. Although my final example was applied to a recursive function that called itself twice in a single expression. The final technique I showed you can be applied to all forms of recursion to yield an iterative version WITHOUT the need to create an explicit stack in the heap. It is the ultimate optimization step in a procedural language. One thing to note is that the final optimization can only be done in a procedural language. For a Functional programming language you will need to utilize another method.
mcguire 8y ago
This seems like a very verbose, kinda-sorta continuation passing approach. Except that he's building the eventual continuation as a list of primitive functions instead of a complex function.
- mcguire 8y ago
  Too late to edit that. Ok, so a CPS transform starts by adding a new parameter, c, which I read "myReturn" or more likely, "returnapotamus". Then, you find the returns in the function and look at the expressions therein. An expression inside cost(...) is left alone, but the expression outside the application of cost is turned into an expression and then to a function that includes a call to returnapotamus, c: def cost2(s, c=lambda s: s): if s <= 1: return c(0) elif s % 2 == 0: return cost2(s // 2, lambda s: c(s + 1)) else: return cost2(s - 1, lambda s: c(min(1 + s, 5))) The initial continuation is just the identity function. cost2 works the same as cost, but it doesn't solve our recursion problem. To do that, we can take Lipport's approach of a pseudo-function built from a stack of primitive functions: def cost3(s): cont = [ lambda s: s ] while s > 1: if s % 2 == 0: cont.append(lambda s: s + 1) s = s // 2 else: cont.append(lambda s: min(s + 1, 5)) s = s - 1 result = 0 while len(cont) > 0: result = cont.pop()(result) return result On the other hand, it's possible to build the continuation as a function, as we go, but it gets a little complicated: def cost5(s): cont = lambda s: s while s > 1: if s % 2 == 0: cont = lambda s, c=cont: c(s + 1) s = s // 2 else: cont = lambda s, c=cont: c(min(s + 1, 5)) s = s - 1 return cont(0) An explanation of what's going on here is beyond the scope of this comment.
- ericlippert 8y ago
  That's correct. I'll discuss CPS in part two.
zozbot123 8y ago
I'm pretty sure that the words "tail recursion" or "tail call" should appear somewhere in this article - see e.g. https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call which also explains in a remarkably simple way how tail recursion relates to iterative constructs (as are found, e.g. in Python). Why do people write 'introductory' articles that don't even mention common terminology?
- mwkaufma 8y ago
  Because the cost() function OP posted isn't doing tail calls and can't be converted into tail call form.
  - mcguire 8y ago
    Not with that kind of attitude. :-) Converting to continuation passing does result in tail calls.
    - mwkaufma 8y ago
      Is there an equivalent of call/cc in Python?
      - mcguire 8y ago
        No, you have to do it manually. I suppose you could write a code-transformer.
- ericlippert 8y ago
  I discuss tail calls in part two. I am often surprised by the number of people who will criticize part one of an article for omitting certain details before reading the second part. Was "part one" unclear in some way?
gweinberg 8y ago
I don't really get the point of this. As far as I can tell, the code is doing the same thing as before but has become (at least to me) much harder to understand.
- mcguire 8y ago
  If the argument to the original function is too large, the function runs out of stack space for the recursion. The function at the end of the post handles much larger arguments. The presentation is very complicated, though.
  - dsamarin 8y ago
    In the end we still have a stack of afters though no?
    - mcguire 8y ago
      Yes, and have to go through and evaluate them. But they are less memory limited than the stack.
- ericlippert 8y ago
  The point is to demonstrate the general truth that any method with a single recursion can be turned into a loop by making a series of small, safe program transformations. It is not intended to be a demonstration of a technique for writing more understandable code.
justinfrankel 8y ago
Am I the only one who read this and thought: hmm, for any number 32 or higher, the minimum cost would always be 5? Who cares about recursion when it's such a constrained problem? :)
- klyrs 8y ago
  It's not as simple as that -- compute the cost of 2^64, 2^64-1, and 2^64-64 to see some more interesting behavior... (I'm using ^ because HN eats double-asterisks; your python may vary)
- ericlippert 8y ago
  You are not the only one who thought that; see the comments to my post. As I note in part two, the point of the article was to show the general method; there are of course many ways to solve the original problem more efficiently. The specific problem is trivial and unimportant.

26 points by wglb 8y ago

Is this programing 101?

Thanks, this is very interesting. I am enrolled in a CS Bsc. (night courses) and while we learned about the different techniques of recursive programming, we never learned how to convert a recursive solution into an iterative one.

iliketosleep 8y ago
I remember when I was at college it was the same, and it doesn't make any sense. I can't recall any instances where I've needed to convert an iterative solution into a resursive one, but there have been countless times I've done the reverse. I belive that the mindless emphasis on resursive programming in college courses has lead to poor practices, where people are using recursion to just make their code more elegant where an iterative solution wouldn't much more complicated but a lot more robust. The result? Down the track, an unforseen use cases resulting in max stack size exceeded errors, causing needless headaches.
- saagarjha 8y ago
  > I belive that the mindless emphasis on resursive programming in college courses has lead to poor practices, where people are using recursion to just make their code more elegant Most courses, especially introductory ones, don’t have particularly good examples of when to use recursion. This doesn’t mean that there aren’t cases where recursion isn’t useful, though.
- gh02t 8y ago
  I think the prevalence of recursion might be attributable to mathematics. A lot of mathematical analysis of algorithms is more natural to express in terms of recursion (partially because of proof by induction), so you often see algorithms stated that way. It's also worth noting that there are plenty of instances where (IMO), recursion is much more natural. For example, traversing trees recursively. I agree, though, there should definitely be more time spent teaching how to convert between the two.
ericlippert 8y ago
One of the reasons I wrote this article was because of exactly the problem that you mention, so I am very happy that you found it interesting! I frequently interview recent CS graduates, and ask a technical question about techniques for removing recursions; the people who do well on such questions tend to have practical experience writing compilers. A lot of these basic techniques are not covered in undergraduate courses, but they are crucial to understanding how modern programming languages work under the hood. I still have my notes from my fourth year course in continuation passing style from my undergrad days and it was very helpful to me when we started adding these concepts to C#.

ciupicri 8y ago

A more stable link would be https://ericlippert.com/2018/12/03/removing-a-recursion-in-python/ https://ericlippert.com/2018/12/03/removing-a-recursion-in-p...

crimsonalucard 8y ago

The article doesn't explain the problem of converting recursion to iteration fully. There is a lot more detail. Most recursion can be implemented using a loop and a stack. If the recursive expression is self contained in the return call, then you don't need a stack. For example: def somefunc(x): if x <= 0: return 0 return somefunc(x-1) is equal to: def somefunc(x) while x > 0: x = x - 1 return x But if the recursion isn't self contained: def somefunc(x): if x == 0: return 0 return somefunc(x-1) + 1 then the iterative version looks like this: def somefunc(x) stack = [] while x > 0: stack.append(x) x = x - 1 while len(stack) != 0: x = x + stack[-1] stack = stack[:-1] return x During Recursion your program will use an internal stack to keep track of previous context. This is called the call stack. Whether or not you use iteration or recursion for the last example you will need a stack. The last example is actually less efficient than the recursive version because you are moving the call stack to the heap. The heap is slower than the call stack but the heap essentially has no limits so you won't encounter stack overflow. In the first example of recursion you will actually benefit from conversion to iteration because you get rid of the stack all together in the iterative example. Some languages will be able to recognize this type of recursion and do an optimization step called "tail-recursion optimization" in which the compiler actually gets rid of the need for a the call stack. Python does not do this, however. The story doesn't end here, however. There are examples of recursion where you cannot create a straightforward iterative version. For example: def somefunc(x): if x <= 0: return 0 return somefunc(x-1) + somefunc(x-2) The straight forward conversion using an explicit stack looks like this: def somefunc(x) stack = [] while x > 0: stack.append(lambda: somefunc(x-2)) x = x - 1 while len(stack) != 0: x + stack[:-1]() stack = stack[:-1] return x You will note that the straightforward conversion doesn't get rid of recursion. The reason is because the previous context is basically another recursive call. You will note that the recursive version of this function actually does the same multiple recursive calls twice which leads to unnecessary repeated calculations. It is possible to optimize this repetition using something called memoization. However memoization requires and does not get rid of recursion. It is not possible to imitate this "inn-efficiency" in an iterative form. The only way to do it is to do an optimization step similar to memoization before iterating. This step, however radically changes the way you think about the problem. It literally reverses the recursion from a top down approach to a bottom up approach. Here is what the iterative form looks like: def somefunc(x): store = [None for _ in range(x)] store[0] = 0 for i in range(1, len(store)): store[i] = store[i-1] + store[i-2] if i-2 >= 0 else 0 return store[-1] This method is called "Dynamic programming using the tabular method." You will note that this version of the function still allocates storage to the heap with "store" There is still a further optimization step you can do here as well. This optimization is basically noticing that you don't need to memorize the entire store in the algorithm. You only need the previous two values. def somefunc(x): store_i_minus_1 = 0 store_i_minus_2 = 0 for i in range(1, len(store)): result = store_i_minus_1 + store_i_minus_2 store_i_minus_1, store_i_minus_2 = result, store_i_minus_1 return result You will note that the the new example has no allocation to the heap and is the full efficient iterative version. Although my final example was applied to a recursive function that called itself twice in a single expression. The final technique I showed you can be applied to all forms of recursion to yield an iterative version WITHOUT the need to create an explicit stack in the heap. It is the ultimate optimization step in a procedural language. One thing to note is that the final optimization can only be done in a procedural language. For a Functional programming language you will need to utilize another method.

mcguire 8y ago

This seems like a very verbose, kinda-sorta continuation passing approach. Except that he's building the eventual continuation as a list of primitive functions instead of a complex function.

mcguire 8y ago
Too late to edit that. Ok, so a CPS transform starts by adding a new parameter, c, which I read "myReturn" or more likely, "returnapotamus". Then, you find the returns in the function and look at the expressions therein. An expression inside cost(...) is left alone, but the expression outside the application of cost is turned into an expression and then to a function that includes a call to returnapotamus, c: def cost2(s, c=lambda s: s): if s <= 1: return c(0) elif s % 2 == 0: return cost2(s // 2, lambda s: c(s + 1)) else: return cost2(s - 1, lambda s: c(min(1 + s, 5))) The initial continuation is just the identity function. cost2 works the same as cost, but it doesn't solve our recursion problem. To do that, we can take Lipport's approach of a pseudo-function built from a stack of primitive functions: def cost3(s): cont = [ lambda s: s ] while s > 1: if s % 2 == 0: cont.append(lambda s: s + 1) s = s // 2 else: cont.append(lambda s: min(s + 1, 5)) s = s - 1 result = 0 while len(cont) > 0: result = cont.pop()(result) return result On the other hand, it's possible to build the continuation as a function, as we go, but it gets a little complicated: def cost5(s): cont = lambda s: s while s > 1: if s % 2 == 0: cont = lambda s, c=cont: c(s + 1) s = s // 2 else: cont = lambda s, c=cont: c(min(s + 1, 5)) s = s - 1 return cont(0) An explanation of what's going on here is beyond the scope of this comment.
ericlippert 8y ago
That's correct. I'll discuss CPS in part two.

zozbot123 8y ago

I'm pretty sure that the words "tail recursion" or "tail call" should appear somewhere in this article - see e.g. https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call which also explains in a remarkably simple way how tail recursion relates to iterative constructs (as are found, e.g. in Python). Why do people write 'introductory' articles that don't even mention common terminology?

mwkaufma 8y ago
Because the cost() function OP posted isn't doing tail calls and can't be converted into tail call form.
- mcguire 8y ago
  Not with that kind of attitude. :-) Converting to continuation passing does result in tail calls.
  - mwkaufma 8y ago
    Is there an equivalent of call/cc in Python?
    - mcguire 8y ago
      No, you have to do it manually. I suppose you could write a code-transformer.
ericlippert 8y ago
I discuss tail calls in part two. I am often surprised by the number of people who will criticize part one of an article for omitting certain details before reading the second part. Was "part one" unclear in some way?

gweinberg 8y ago

I don't really get the point of this. As far as I can tell, the code is doing the same thing as before but has become (at least to me) much harder to understand.

mcguire 8y ago
If the argument to the original function is too large, the function runs out of stack space for the recursion. The function at the end of the post handles much larger arguments. The presentation is very complicated, though.
- dsamarin 8y ago
  In the end we still have a stack of afters though no?
  - mcguire 8y ago
    Yes, and have to go through and evaluate them. But they are less memory limited than the stack.
ericlippert 8y ago
The point is to demonstrate the general truth that any method with a single recursion can be turned into a loop by making a series of small, safe program transformations. It is not intended to be a demonstration of a technique for writing more understandable code.

justinfrankel 8y ago

Am I the only one who read this and thought: hmm, for any number 32 or higher, the minimum cost would always be 5? Who cares about recursion when it's such a constrained problem? :)

klyrs 8y ago
It's not as simple as that -- compute the cost of 2^64, 2^64-1, and 2^64-64 to see some more interesting behavior... (I'm using ^ because HN eats double-asterisks; your python may vary)
ericlippert 8y ago
You are not the only one who thought that; see the comments to my post. As I note in part two, the point of the article was to show the general method; there are of course many ways to solve the original problem more efficiently. The specific problem is trivial and unimportant.