I hope it is clear that at every small refactoring we have maintained the meaning of the program. Īfter = get_after(s) # after is a function!Īnd you know, let’s make this a little bit more general, and make the recursive case a bit more concise. Notice that we have a function which returns a function here!. The third step is: I want to decide which function to call afterwards in a helper function. The second step is: I want to compute the argument in a helper function. The first step of our transformation is: I want the thing that precedes every recursive call to be a computation of the argument, and the thing that follows every recursive call to be a return of a method call that takes the recursive result: def add_one(n): Let’s see first how to get the program into that form. What I’d like to show here is that to remove this sort of recursion, you can do so by re-organizing the code using a series of small, careful refactorings until the program is in a form where removing the recursion is easy. There are probably more Pythonic solutions using generators and so on. Of course, the technique that I’m going to show you is not necessarily “Pythonic”. The point is that we can refactor any simple recursive method to remove the recursion this is just the example that was at hand. Rather, it was just a jumping-off point for the question of how to in general remove a single recursion from a Python program. The question then is: how do we transform this recursive algorithm into an iterative algorithm in Python?īefore we get into it, of course there are fast ways of solving this specific problem I’m not interested in this problem per se. However, apparently the user was experimenting with values so large that the program was crashing from exceeding the maximum recursion depth! Those must have been some big numbers. If s % 2 = 0 : return 1 + cost (s // 2 ) return min(1 + cost(s - 1), 5) The problem is: given the space the player is on, what is the lowest cost in coins to get home? The recursive solution is straightforward: def cost (s ): if s <= 1:
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |