Recursion

What Is 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

Recursive Calculation of Factorial

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

Recurrent Definition

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

Finding a Recurrent Dependence

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

Factorial Implementation

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

Example of 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:

F1 = F2 = 1

Fi = Fi-1 + Fi-2 (for i > 2)

Proceeding directly from the definition, we can implement the following recursive method for finding the nth Fibonacci number:

Recursion

Example of 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

Simulation of N Nested Loops

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

Simulation of N Nested Loops

N = 31 1N = 31 1 1
1 21 1 2
1 31 1 3
2 11 2 1
K = 32 2K = 3...
2 33 2 3
3 13 3 1
3 23 3 2
3 33 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