subroutines. 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:

A certain 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

Recursion is a way of defining a set of objects in terms of the set itself, based on given simple base cases.

Recursive will also be called a procedure (function) that calls itself directly or through other procedures and functions
An example of a recursive procedure:

procedure Rec(a: integer);
begin
    if a > 0 then
        Rec(a - 1);
    write(a);
end;

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

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 at all, for example, Prolog. 
Let's try to simulate the operation of the for loop. 
The for loop contains a step counter variable. In a recursive subroutine, such a variable can be passed as a parameter.

//LoopImitation() procedure with two parameters
//First parameter – step counter, second parameter – total number of steps
procedure LoopImitation(i, n: integer);
begin
    writeln('Hello N ', i); // Operator to be repeated for any value of i
    if i < n then //Until the loop counter becomes equal to the value n,
        LoopImitation(i + 1, n); //call a new instance of the procedure, with the parameter i+1 (transition to the next value i)
end; 

Iteration in programming — in a broad sense — organization of data processing, in which actions are repeated many times, without leading to calls to themselves (unlike  %BA%D1%83%D1%80%D1%81%D0%B8%D1%8F" title="Recursion">Recursions). In the narrow sense — one step 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:



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

The recursive factorial function would look like this	Compare the algorithm for finding the factorial in the usual, non-recursive way
function Factorial(n: integer): integer; begin     if n > 1 then         Factorial := n * Factorial(n - 1)     else         Factorial := 1; end;	x := 1; for i := 2 to n do     x := x * i; writeln(x);

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.