How do experienced programmers in particular think about recursion, how do they perceive it?

I am sorting out a quick sort, acting as an interpreter and starting to get confused as I delve into recursion.

def quick_sort(alist): if len(alist) <= 1: return barr = alist[0] left = [] mid = [] right = [] for i in range(len(alist)): if alist[i] < barr: left.append(alist[i]) elif alist[i] > barr: right.append(alist[i]) else: #alist[i] == bar mid.append(alist[i]) quick_sort(left) # Отсортировать левую часть quick_sort(right) # Отсортировать правую часть k=0 for x in left+mid+right: alist[k] = x k+=1 return alist alist = [2,3,4,1] print(quick_sort(alist))

In many video tutorials, in a line of code, when a function calls itself, the teacher treats the function as already written.

Is it really that simple and you should not even try to read recursive functions like normal ones.

Particularly interesting is how to read recursion in the context of this algorithm!

Ps. I know the rules of recursion: read from the end, the base case, the recurrence relation.

  • 2
    Recursion is no different from a normal function, it is “almost” equivalent to calling a function in a loop in the general case. - Vladimir Klykov
  • four
    Recursion is the most common function call, just a function calls itself, xs what else to think, why “read from the end” and other perversions - andreymal
  • Experienced programmers have developed abstract thinking, so they have ways to think about matters that are much more complex than recursion. - Sergey Gornostaev
  • one
    I always try to avoid them, recursion is evil! - Isaev
  • Regarding qsort, it would be nice to understand that in practice it always follows: 1) when recursively calling, start with a short segment (this minimizes the depth); 2) do not reach the end, i.e. shorter segments, say, 20 elements need to be sorted by another method (for example, sorting by inserts (this will increase the speed)) - avp

5 answers 5

It is convenient to consider any recursive function through its call tree ( eng. Call stack tree ):

enter image description here

Where each vertex is the place where the function is called, and the branches, oddly enough, branching is a recursive call.

It is important to highlight 2 points in the code:

  1. breakpoint
  2. place of recursive call or, in other words, "branch point"

In general, it looks like this:

 def rec_func(...): if(stop_condition): <-- точка останова return ... rec_func(...) <-- ветвление rec_func(...) <-- ветвление return ... <-- "главный" return текущей вершины

Now let's sort the Quick Sort from the question:

Logic itself is quite simple in nature:

  1. divide an array by some criterion, in this algorithm, depending on the special value of pivot, until arrays of unit length are obtained — arrays of unit length cannot be unordered.
  2. to collect an array of the resulting sorted elements

The secret lies in the first paragraph - you need to divide the arrays in half relative to some element, it is usually called a pivot. The breakpoint in this algorithm is also quite obvious - if(размер текущего массива <= 1) .

From all this we get such a tree in the case when pivot is always the last element:

enter image description here

In your code, the first element is always used as a pivot, but this does not change the essence of the algorithm.

All vertices without descendants are the unit arrays that we were looking for; their "concatenation" into the final array from left to right will be the desired sorted array.

Each vertex of this tree is a call to a recursive function that divides this array.

Pivot and its equal elements are written into the "central" array, which does not need to be sorted or transferred somewhere.

And finally, back to Fibonacci, from which I began to answer. The straightforward code of this algorithm is as simple as a cork:

 def F(n): if n == 0: return 0 <-- точка останова elif n == 1: return 1 <-- точка останова else: return F(n-1)+F(n-2) <-- 2 точки ветвления, получаем бинарное дерево

By the way, the call tree for calculating the Fibonacci number shows why recursion is bad for this case. In the tree there are whole branches with the same calculations.

    Recursion is similar to induction proof, which mathematicians themselves admit is not obvious.

    Therefore, if recursion is incomprehensible from the first time, you just need to consider it with a few examples. I would recommend examples that work with tree structures, as they are well visualized.

    Imagine a binary tree. If the tree is small and consists of one node, then its height is equal to one. If this node has one or two children, then the height is two. How to write a program that calculates the height of the tree?

    Recursion is perfect here. First, we set a general rule: the height of a binary tree is one plus the maximum of the heights of its child trees.

     int getHeight(BinaryTree binaryTree) { int leftHeight = getHeight(binaryTree.left); int rightHeight = getHeight(binaryTree.right); return 1 + max(leftHeight, rightHeight); }

    Such a function is not entirely correct, because it will never stop and will call itself until the stack overflows.

    We can stop it if we get to the degenerate case. For example, we can assume the height of the empty subtree is zero, that is, getHeight(null) == 0 .

    Then the function takes the form:

     int getHeight(BinaryTree binaryTree) { if (binaryTree == null) return 0; int leftHeight = getHeight(binaryTree.left); int rightHeight = getHeight(binaryTree.right); return 1 + max(leftHeight, rightHeight); }

    So we wrote a recursive calculation function. Here it is important to distinguish two parts of the recursive function that coincide with the proof by induction.

    Part one: the general rule. Our algorithm should express the calculation of something through the same calculation, but for a smaller structure. Part two: stop. At the end of the computation there must be a degenerate case, which is considered not recursive, but trivial. Let's say the height of an empty tree is zero. The factorial unit is equal to one. And stuff like that.

    Another example is arithmetic expressions. Take this:

     g * h * i + k ^ l ^ m

    Despite the fact that this expression does not look like a tree, in reality, we can present it in a tree form that will allow it to be calculated. This is what this tree looks like:

      + * ^ * ik ^ ghlm

    In the tree nodes there are operators, in our case this is addition + , multiplication * and raising to a power ^ . Child elements are other expressions.

    The function of calculating the value of the expression will look like this:

     double calculate(Expression expression) { double left = calculate(expression.left); double right = calculate(expression.right); switch (expression.operator) { case '+': return left + right; case '*': return left * right; case '^': return pow(left, right); default: throw new Exception(); } }

    Now we need to find degenerate cases to stop the recursive output. These are cases where the expression is a single variable g or i . The value of such an expression is the value of the variable itself. Suppose that for such variables we have in the expression object the field of operator is equal to 'v' and the value of such a variable is stored in the associative array variables . Then the function would look like this:

     double calculate(Expression expression) { if (expression.operator == 'v') return variables[expression.name]; double left = calculate(expression.left); double right = calculate(expression.right); switch (expression.operator) { case '+': return left + right; case '*': return left * right; case '^': return pow(left, right); default: throw new Exception(); } }

    This function is not very good, because in OOP-language one should use the polymorphic method instead of switch . But even in OOP language, polymorphic methods still recursively call each other.

    For training, we can use a not very correct, but understandable option. Now try to solve the recursion problem yourself, for example, the well-known problem about the Hanoi tower. After a few such tasks, there will be no more recursion problems.

      I will give an example of writing a simple recursive function for unpacking nested lists with comments, I hope someone will come in handy:

      Suppose we have a list, you need to unpack nesting:

       t = [1, 2, [3, 4, [5]]]

      Thus, we begin to write a function, at the input I will have a list:

       def extract(li):

      It is immediately important to note that since the results are related, it means that you need to carry the result of all the other calls with you, so the input parameters should include our result, our answer list, well, let the list be empty:

       def extract(li, result=[]):

      Then we write the body of the function in this example, looping over the elements:

       for i in li:

      Now the branch step has come, it is necessary to define the case when the function calls itself, for this example, this condition will check whether the element is a list:

       if isinstance(i, list): extract(i, result)

      Well, let's define an ordinary case - which is also a way out of recursion, in this case, exit from call recursion is to go to an empty list or to an item that is not a list:

       else: result.append(i)

      We finish the function with the command return , with which we started the order and finished:

       return result

      Total:

       t = [1, 2, [3, 4, [5]]] def extract(li, result=[]): for i in li: if isinstance(i, list): extract(i, result) else: result.append(i) return result print extract(t) # [1, 2, 3, 4, 5]

      Give the input something “such” to see how the function behaves:

       print extract([1, 2, [3, [], [5]]], []) print extract([{}, 2, [[[[[[3]]]]]]], []) # [1, 2, 3, 5] # [{}, 2, 3]

        You are too complicated. No need to dwell on the fact that the function calls itself. Think of the function as a black box. When you call a normal function, do not climb how to see how it works? You only need to know what it gets at the entrance and what it returns at the output. The same applies to the recursive function, it does not matter that it is still being written. Do not try to unwind the entire chain of calls in your head.

          In order not to dwell on "Repeat", it is better to investigate recursion not "from the top down", but "from the bottom up", that is, from the final condition that interrupts the recursion. For example, it is better to start calculating the Fibonacci sequence from the condition "if a == 1, then return 1" until the number of returns is equal to the desired value.

          • one
            The author has already said about this in question. Yes, and this statement is not quite true, breakpoints are always written before the recursive call. - RiotBr3aker
          • @ RiotBr3aker needs to start from the end, otherwise it will be like with the expression "this statement is a lie." - Adokenai
          • Breakpoints usually look very obvious, so I’ll stay with my opinion. However, this post is not the answer to the question. - RiotBr3aker