Recursion is a technique where the same function is called inside its own definition. It has wide applications in different scenarios. Recursion helps us to break down a problem into simpler steps and solve them more easily.

However, recursion consumes a lot of memory and should be carefully used. Otherwise, it can cause memory leaks or program crashes.

Recursive Function in C++

Functions that follow/implement recursion are called recursive functions. It simply calls itself to create a loop effect.

Syntax of a Recursive Function

void myfunc() {
  /* this will call myfunc() again in turn */
  myfunc();
  // other code…
}

The inner function must be completely executed before the outer function. It must be defined in such a way that the function does not keep on executing forever or it will crash the program.

Iteration vs Recursion

Iteration is the process of repeatedly executing a certain code a number of times. It is implemented using loops like for and while. However, recursion involves the use of functions. By calling the same function inside its definition, we can execute it repeatedly. It is slower than iteration because every time a new function has to be created and added to the call stack.

void main() {
  while (true) {
    // infinite loop using iteration
  }
}
void func() {
  // infinite loop using recursion
  func();
}

If a solution for a problem exists using recursion, we can also use iteration to achieve the same. Moreover, the recursive approach is simpler to code but slower than the iterative approach.

Defining a recursive function

Before defining a recursive function, we must follow a few important rules:

1- Have a base case

A base case is a condition that is used to stop the recursion from running forever. A recursive function should be designed such that it approaches the base case at some point.

Every recursive call should get closer to reaching the base case so that it terminates.

2- Place the recursive function call at the right location.

We can call the recursive function at any place in the function body. But the lines of code that come after the recursive call are only executed once the nested calls have finished executing.

3- Do not call the recursive function in the base case

If the base case is reached, it should return a definite value and end the current function execution in the stack.

Case Study: Finding Factorial of a number

Factorial of a number n is a mathematical operation that returns the product of all the natural numbers that are equal or less than n.

Factorial of 3 is 3 x 2 x 1 = 6, and for 6 it is 6 x 5 x 4 x 3 x 2 x 1 = 720

To find the factorial of a number, we can either use an iterative or a recursive approach to solve this problem.

Iterative Approach

int factorial = 1, n = 6;
int num = n;
while(n >= 1){
factorial= factorial * n;
n = n - 1;
}
cout<<" The factorial of "<< num <<" is "<< factorial;

Recursive Approach

int factorial(int n) {
  /* 1. Base case :: runs when n is less than or equal to 1 */
  if (n <= 1) {
    /* 2. Never call the recursive function inside the base case */
    return 1;
  } else {
    /* 3. Every time the recursive function is called, we pass a
    number one less than the current one. This is how it reaches the base case. */
    return n * factorial(n– 1);
  }
}
void main() {
  int n = 6;
  court << " The factorial of " << n << " is " << factorial(n);
}

Analyzing the recursive calls

When n is 6 and factorial(n) is called, it expands into the following recursive calls:

factorial(6);
= 6 * factorial(5);
= 6 * 5 * factorial(4);
= 6 * 5 * 4 * factorial(3);
= 6 * 5 * 4 * 3 * factorial(2);
= 6 * 5 * 4 * 3 * 2 * factorial(1);
/* After the expansion is complete and the base case is reached, it then terminates one by one */
= 6 * 5 * 4 * 3 * 2 * 1; [factorial(1) terminates returning 1]
= 6 * 5 * 4 * 3 * 2; [factorial(2) terminates returning 2]
= 6 * 5 * 4 * 6; [factorial(3) terminates returning 6]
= 6 * 5 * 24; [factorial(4) terminates returning 24]
= 6 * 120; [factorial(5) terminates returning 120]
= 720; [factorial(6) finally terminates returning 720 as the final result]

First, the inner function must complete execution. So, for factorial(6) to finish executing, factorial(5) must complete and for it, factorial(4) must finish, and so on till it reaches the base case.

Other Applications

Recursion is useful to find many other solutions like finding Fibonacci Numbers, Traversing a tree data structure, etc. Practical applications include expanding a directory to list all its files and subdirectories, updating a nested pattern of data, etc.

Points to Remember