(Python) Subroutines. recursion

Recursion

A procedure or function may contain a call to another procedure within it. Including, the subroutine can call itself. In this case, the computer doesn't care. He also, as always, consistently executes the commands that he met from top to bottom.

If you remember mathematics, then there you can meet the principle of mathematical induction. It is as follows:
some statement is true for every natural n if
    1. it is valid for n = 1 and
    2. from the validity of the statement for any arbitrary natural n = k it follows that it is true for n = k + 1.

In programming, this technique is called recursion.
   

Example

def Rec(a):
    if (a>0): Rec(a-1)
    print(a)

Schematically, the work of recursion can be represented by a flowchart



The Rec() procedure is executed with parameter 3. Then, inside the procedure with parameter 3, the procedure with parameter 2 is called, and so on, until the procedure with parameter 0 is called. When the procedure with parameter 0 is called, the recursive call will no longer occur and the procedure with parameter 0 will print the number 0 and exit. Then control is transferred back to the procedure with parameter 1, it also finishes its work by printing the number 1, and so on. before the procedure with parameter 3. 

All called procedures are stored in memory until they complete their work. The number of concurrent procedures is called recursion depth.
 

Recursion as a loop replacement

We have seen that recursion is the repeated execution of contained instructions in a subroutine. And this, in turn, is similar to the work of the cycle. There are programming languages ​​in which the loop construct is absent altogether. For example, Prolog. 
Let's try to simulate the work of the loop for. 
The for loop contains a step counter variable. In a recursive subroutine, such a variable can be passed as a parameter.

# Procedure LoopImitation() with two parameters
# First parameter – step counter, second parameter – total number of steps
def LoopImitation(i, n):
    print("Hello N", i) # Statement to be repeated for any value of i
    if i < n: # Until the loop counter equals the value n,
        LoopImitation(i + 1, n) # call a new instance of the procedure,
                                # with parameter i+1 (go to next value i)

Recursion and iteration

Iteration in programming - one stepof a cyclic data processing process. 
Often iterative algorithms at the current step (iteration) use the result of the same operation or action calculated at previous steps.  One example of such calculations is the calculation of recurrence relations. 
A simple example of a recursive value is the factorial: \(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\).
The calculation of the value at each step (iteration) is \(N=N \cdot i\) .  When calculating the value of \(N\), we take the already stored value \(N\).< br />
The factorial of a number can also be described using the recurrent formula:
\(\begin{equation*} n!= \begin{cases} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{cases} \end{equation*}\)

You may notice that this description is nothing more than a recursive function.
Here the first line (\(n <= 1\)) is the base case (recursion termination condition) and the second line is the transition to the next step. 

Recursive factorial function	Iterative algorithm
def Factorial(n): if n > 1: return n * Factorial(n - 1) else:   return 1	x=1 for i in range(1, n + 1): x = x * i;

It should be understood that function calls involve some additional overhead, so a non-recursive factorial calculation will be slightly faster. 

Conclusion: where you can write a program with a simple iterative algorithm, without recursion, then you need to write without recursion. But still, there is a large class of problems where the computational process is implemented only by recursion.
On the other hand, recursive algorithms are often more understandable.
 

Task

In the alphabet of the language of the tribe «Tumba-Yumba» four letters: "K", "L", "M" and "N". It is necessary to display on the screen all words consisting of n letters that can be built from the letters of this alphabet

The problem is a normal brute-force problem that can be reduced to a smaller problem.
We will sequentially substitute letters for the word.
The first position of a word can be one of the 4 letters of the alphabet (K, L, M, N).
First, put the letter 'K' first. Then, in order to get all variants with the first letter 'K', you need to enumerate all possible combinations of letters in the remaining n-1 positions and .etc. (see picture) Thus, we came up with a recursive solution: in a loop, go through all possible first letters (putting each letter of the alphabet in turn in the first place) and for each case build all possible "tails"; length n-1.
 

Recursive iteration of characters

You need to stop the recursion and output the finished word when the remaining part is empty (n = 0), i.e. all letters are already selected. 
The recursive procedure would look like this: 

def TumbaWords(word, alphabet, n):
    if n < 1:
        print(word)
        return
    for c in alphabet:
        TumbaWords(word+c, alphabet, n - 1)