📜 ⬆️ ⬇️

Eliminating recursion in Python

Hi, Habr! I present to you the translation of the article "Removing a recursion in Python, part 1" by Eric Lippert.


Over the past 20 years, I have admired the simplicity and capabilities of Python, although in fact I have never worked with it and have not studied it in detail.


Recently, I looked at him closer - and it turned out to be a really pleasant language.


A recent question on StackOverflow made me think about how to convert a recursive algorithm into an iterative algorithm, and it turned out that Python is quite a suitable language for this.
The problem faced by the author of the question was as follows:



The question is: what is the smallest amount of coins you need to pay to return from the current cell to the first one.


The task has an obvious recursive solution:


def cost(s): if s <= 1: return 0 if s % 2 == 0: return 1 + cost(s // 2) return min(1 + cost(s - 1), 5)

However, this program fell, reaching a maximum recursion depth, most likely due to the fact that the author of the question experimented with very large numbers.
Therefore, the question arises: how to turn a recursive algorithm into an iterative algorithm in Python?


Before we begin, I want to note that of course there are faster solutions to this particular problem, in itself it is not very interesting.


Rather, this task served only as a starting point in the question of how to generally get rid of a single recursive call in a Python program.


The point is that you can transform any simple recursive method and get rid of recursion, and this is just an example that was at hand.


The technique I’m going to show, of course, doesn’t quite correspond to how it is customary to write in Python, probably a solution in Python-style would use generators or other language features.


What I want to show here is how to get rid of recursion, using a sequence of small and safe transformations that lead the function to a form in which it is easy to replace recursion with iteration.


To begin, let's see how to bring the program to this form.


At the first step of our transformation, I want the calculations made before the recursive call to be reduced to the calculation of the argument, and the calculations, after the recursive call, are performed in a separate method that accepts the result of the recursive call.


 def add_one(n): return n + 1 def get_min(n): return min(n + 1, 5) def cost(s): if s <= 1: return 0 if s % 2 == 0: argument = s // 2 result = cost(argument) return add_one(result) argument = s - 1 result = cost(argument) return get_min(result)

The second step I want to make the calculation of the argument in a separate function:


 # ... def get_argument(s): if s % 2 == 0: return s // 2 return s - 1 def cost(s): if s <= 1: return 0 argument = get_argument(s) result = cost(argument) if s % 2 == 0: return add_one(result) return get_min(result)

In the third step, I want to add an auxiliary function that will select the continuation function called after returning from recursion.


Note that the helper function returns a function.


 #... def get_after(s): if s % 2 == 0: return add_one return get_min def cost(s): if s <= 1: return 0 argument = get_argument(s) after = get_after(s) # after это функция! result = cost(argument) return after(result)

Now we write this in a more general and concise form:


 #... def is_base_case(s): return s <= 1 def base_case_value(s): return 0 def cost(s): if is_base_case(s): return base_case_value(s) argument = get_argument(s) after = get_after(s) return after(cost(argument))

It can be seen that each change made has retained the meaning of the program.


Now the parity check of the number is performed twice, although before the changes there was only one check.


If we want, we can solve this problem by combining two auxiliary functions into one that returns a tuple.


But let's not worry about this as part of the solution to this problem.


We have reduced our recursive method to the most general form.



Something important to pay attention to at this step is that after should not contain cost calls itself.


The method I show here removes a single recursive call.


If you have 2 or more recursions, then we will need another solution.


Once we have brought our recursive algorithm to this form, it is easy to convert it to iterative.


The trick is to present what is happening in the recursive program.


How we do recursive descent: we call get_argument before the recursive call and call the after function after returning from recursion.


That is, all get_argument calls occur before all after calls.
Therefore, we can convert this to 2 cycles: the first one calls get_argument and forms the list of after functions, and the second one calls all after functions:


 #... def cost(s): # Создаём стек из функций "after". Все эти функции # принимают результат рекурсивного вызова и возвращают # значение, которое вычисляет рекурсивный метод. afters = [ ] while not is_base_case(s): argument = get_argument(s) after = get_after(s) afters.append(after) s = argument # Теперь у нас есть стек функций "after" : result = base_case_value(s) while len(afters) != 0: after = afters.pop() result = after(result) return result

No more recursion!


It looks like magic, but all that we are doing here is the same thing that the recursive version of the program did and in the same order.


This example reflects the idea that I often repeat about the call stack: its purpose is to communicate what will happen next, not what has already happened!


The only useful information in the call stack in the recursive version of the program is what the value of the after is , since this function is called next, and everything else on the stack is not important.


Instead of using the call stack as an inefficient and cumbersome way of storing the stack after , we can simply store the stack of functions after .


Next time we will look at a more complicated way to remove recursion in Python.



Source: https://habr.com/ru/post/440178/

More articles: