Recursive functions

Location
  1. Courses

    /

  2. Complete C++ Course

    /

  3. The basics

    /

  4. Recursive functions

What is a recursive function?

A recursive function is simply a function that calls itself back. In general, it is best to avoid them if we seek maximum performance (Because of the overhead of function calling). However, most of the time, a recursive function is made of way fewer lines of code than an equivalent non-recursive function.

In a recursive function, there must be a condition where it stops calling itself back, otherwise it would call itself back infinitely and the program would crash because of stack overflow.

The following function would end up making the program crash since it never stop calling itself back:

void func(unsigned a) { unsigned b = 2*a; func(b); }

The following function:

void func(unsigned a) { unsigned b = 2*a; if(b < 1000) func(b); }

Would not make the program crash, because it stops before calling itself back too many times. A recursive function does not need to be calling itself back infinitely to make the program crash. If it calls itself back enough times to make the stack overflow, it will make the program crash.

Example

In this example, we will code a function that calculates the factorial of an unsigned integer. For those who do not know, the factorial of a positive integer is the integer multiplied by all the positive integers that are smaller than it, until 1. For example, the factorial of 5 is (5*4*3*2*1) which equals 120.

Note that performance-wise, using recursive functions to calculate the factorial of a number is far from optimal, but the code is short and easy to understand.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream> unsigned long long factorial(unsigned long long n) { if(n == 0) // The factorial of 0 is 1. return 1; return n * factorial(n-1); } int main() { std::cout << factorial(5) << std::endl; std::cout << factorial(7) << std::endl; std::cout << factorial(10) << std::endl; std::cout << factorial(15) << std::endl; std::cout << factorial(25) << std::endl; return 0; }

Note that the result of the factorial increases extremely fast relatively to the number the factorial is calculate on. Be aware that the factorial easily produces a number that is too big for an unsigned long long variable to hold. A way to increase the number of values the factorial function can produce would be to replace the type unsigned long long by double long. It would however be at the cost of precision.

Calculating the factorial with a non-recursive function

The same example, but with a non-recursive (and way more efficient) function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream> unsigned long long factorial(unsigned long long n) { if(n < 2) // The factorial of 0 and 1 is 1. return 1; /* Here, if n equals 0, then n2 is assigned with the biggest value it can hold. This is why the function returns 1 if n == 0 (Or 1). */ unsigned long long n2 = n-1; while(n2 > 1) { n *= n2; n2--; } return n; } int main() { std::cout << factorial(5) << std::endl; std::cout << factorial(7) << std::endl; std::cout << factorial(10) << std::endl; std::cout << factorial(15) << std::endl; std::cout << factorial(25) << std::endl; return 0; }