Skip to main content

Recursive functions

Let us consider recursive functions separately. A recursive function is a construction in which a function calls itself.

Recursive factorial function​

For example, let's take the factorial calculation that uses the formula n! = 1 * 2 * ... * n. That is, in essence, to find the factorial of a number, we multiply all the numbers up to that number. For example, the factorial of the number 4 is 24 = 1 * 2 * 3 * 4, and the factorial of the number 5 is 120 = 1 * 2 * 3 * 4 * 5.

Let's define a method for finding the factorial:

int Factorial(int n)
{
    if (n == 1) return 1;

    return n * Factorial(n - 1);
}

When creating a recursive function, it must necessarily contain some base variant from which the function starts calculating. In the case of a factorial, it is the factorial of the number 1, which is equal to 1. The factorials of all other positive numbers will start by calculating the factorial of the number 1, which is equal to 1.

At the programming language level, the return operator is used to return the base case:

if (n == 1) return 1;

That is, if the input number is equal to 1, then 1 is returned

Another feature of recursive functions: all recursive calls must refer to subfunctions that eventually converge to the base case:

return n * Factorial(n - 1);

Thus, if you pass a number that is not equal to 1 to a function, further recursive calls to subfunctions will pass a number smaller by one each time. Eventually we will reach the situation when the number is equal to 1, and the base case will be used. This is the so-called recursive descent.

Let's use this function:

int Factorial(int n)
{
    if (n == 1) return 1;

    return n * Factorial(n - 1);
}

int factorial4 = Factorial(4); // 24
int factorial5 = Factorial(5); // 120
int factorial6 = Factorial(6); // 720

Console.WriteLine($“Factorial of the number 4 = {factorial4}”);
Console.WriteLine($“Factorial of number 5 = {factorial5}”);
Console.WriteLine($“Factorial of number 6 = {factorial6}”);

Let's look step-by-step at what happens in the case of calling Factorial(4).

  1. First we check if the number is equal to one:
if (n == 1) return 1;

But at first n is equal to 4, so this condition is false and the code is executed accordingly

return n * Factorial(n - 1);

So in fact we have:

return 4 * Factorial(3);
  1. Then the expression is executed:
Factorial(3)

Again, n is not equal to 1, so the code is executed

return n * Factorial(n - 1);

So in effect:

return 3 * Factorial(2);
  1. Next, the expression is executed:
Factorial(2)

Again, n is not equal to 1, so the code is executed

return n * Factorial(n - 1);

So in effect:

return 2 * Factorial(1);
  1. Next, the expression is executed:
Factorial(1)

Now n is equal to 1, so the code is executed

if (n == 1) return 1;

And 1 is returned.

Finally, the expression

Factorial(4)

In reality, it turns out to be

4 * 3 * 2 * Factorial(1).

Recursive Fibonacci function​

Another common illustrative example of a recursive function is the function that calculates Fibonacci numbers. The nth term of the Fibonacci sequence is determined by the formula: f(n)=f(n-1) + f(n-2), with f(0)=0 and f(1)=1. That is, the Fibonacci sequence will look like 0 (0th member), 1 (1st member), 1, 2, 3, 5, 8, 8, 13, 21, 21, 34, 34, 55, 55, 89, 144, ..... To determine the numbers of this sequence, let's define the following method:

int Fibonachi(int n)
{
    if (n == 0 || n == 1) return n;
    
    return Fibonachi(n - 1) + Fibonachi(n - 2);
}

int fib4 = Fibonachi(4);
int fib5 = Fibonachi(5);
int fib6 = Fibonachi(6);

Console.WriteLine($“4 Fibonacci number = {fib4}”);
Console.WriteLine($“5 Fibonacci number = {fib5}”);
Console.WriteLine($“6 Fibonacci number = {fib6}”);

Here the base case looks like the following:

if (n == 0 || n == 1) return n;

That is, if we are looking for the zero or the first element of the sequence, the same number, 0 or 1, is returned. Otherwise, the result of the expression Fibonachi(n - 1) + Fibonachi(n - 2) is returned;

Recursions and loops​

These are the simplest examples of recursive functions that are meant to give an understanding of how recursion works. For both functions, however, you can use cyclic constructs instead of recursions. And typically, loop-based alternatives are faster and more efficient than recursion. For example, calculating Fibonacci numbers using loops:

static int Fibonachi2(int n)
{
	int result = 0;
	int b = 1;
	int tmp;

	for (int i = 0; i < n; i++)
	{
		tmp = result;
		result = b;
		b += tmp;
	}

	return result;
}

At the same time, recursion provides an elegant solution in some situations, such as when traversing various tree views, for example, a tree of directories and files.