Recursion

We call an object **recursive** if it contains itself, or if it is defined by itself.

**Recursion** is a programming technique in which a method makes a call to itself to solve a particular problem. Such methods are called **recursive**.

**Recursion** is a programming technique whose correct usage leads to elegant solutions to certain problems. Sometimes its usage could considerably simplify the programming code and its readability.

Recursion

Factorial of n (written n! ) is the product of all integers between 1 and n inclusive

By definition 0! = 1.

n! = 1.2.3...n

When creating our solution, it is much more convenient to use the corresponding recurrent definition of factorial:

n! = 1, for n = 0

n! = n.(n-1)!, for n>0

Recursion

The presence of recurrent dependence is not always obvious. Sometimes we have to find it ourselves. In our case we can do this by analyzing the problem and calculating the values of the factorial for the first few integers.

0! = 1 1! = 1.1 = 1.0! 2! = 2.1 = 2.1! 3! = 3.2.1 = 3.2! 4! = 4.3.2.1 = 4.3! 5! = 5.4.3.2.1 = 5.4!

From here you can easily see the recurrent dependability:

n! = n.(n-1)!

Recursion

long factorial(int n){ if(n <= 1){ return 1; } return n * factorial(n - 1); }

Recursion

Let’s consider the Fibonacci numbers. These are the elements of the following sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Each element of the sequence is formed by the sum of the previous two elements. The first two elements are equal to 1 by definition, i.e. the next two rules apply:

F_{1} = F_{2} = 1

F_{i} = F_{i-1} + F_{i-2} (for i > 2)

Proceeding directly from the definition, we can implement the following **recursive** method for finding the n^{th} Fibonacci number:

Recursion

int fibonacci(int n){ if(n <= 2){ return 1; } return fibonacci(n - 1) + fibonacci(n - 2); }

This example shows how simple and natural the implementation of a solution
can be when using **recursion**

On the other hand, it can serve as an example of how attentive we have to be while programming with recursion. Although it is intuitive, the present solution is one of the classical examples when the usage of **recursion** is highly inefficient as there are many excessive calculations (of one and the same element of the sequence) due to the **recursive** calls

Recursion

Very often we have to write **nested loops**. It is very easy when they are two, three or any number previously assigned. However, if their count is not known in advance, we have to think of an alternative approach. This is the case with the following task.

Write a program that simulates the execution of N **nested loops** from 1 to K, where N and K are entered by the user. The result of the performance of the program should be equivalent to the execution of following fragment:

for(int i1 = 1; i1 <= k; ++i1){ for(int i2 = 1; i2 <= k; ++i2){ for(int i3 = 1; i3 <= k; ++i3){ .... for(int in = 1; in <= k; ++in){ printf("%d %d %d ... %d", i1, i2, i3, ..., in); } } } }

Recursion

N = 3 | → | 1 1 | N = 3 | → | 1 1 1 |

1 2 | 1 1 2 | ||||

1 3 | 1 1 3 | ||||

2 1 | 1 2 1 | ||||

K = 3 | 2 2 | K = 3 | ... | ||

2 3 | 3 2 3 | ||||

3 1 | 3 3 1 | ||||

3 2 | 3 3 2 | ||||

3 3 | 3 3 3 |

The algorithm for solving this problem is not as obvious as in the previous example. Let’s consider two different solutions - one recursive, and one iterative

Each row of the result can be regarded as ordered sequence of N numbers. The first one represents the current value of the counter of the loop, the second one – of the second loop, etc. On each position we can have value between 1 and K. The solution of our task boils down to finding all ordered sequences of N elements for N and K given