Recursion in C++

Recursion refers to a process that repeats itself until it has achieved its goal. This process repeats itself in terms of its own updated version. Commonly, when a process repeats itself, it is called Recursion.

1. Programming Definition
2. Importance of Recursion
3. Use of Recursion
4. How Recursion Operates
5. Example Functions
6. Application: Factorial
7. Memory Allocation
8. Direct Recursion vs Indirect Recursion
9. Tailed and Non-tailed Recursion
10. Recursive Data Structures in C++
11. Stack Overflow in Recursion

Programming Definition

In computer science, one has to work on finding optimal solutions to problems that occurred. These problems could range from a simple calculation to building a full-fledged project. For this, computer scientists usually break more significant problems into small portions. Then, they solve those problems to get the final result at the end. Recursion is known to solve small instances of the problem and provide the solution efficiently.

Importance of Recursion

Comparison with Loops and Iterations

Usually, programmers use iterations to solve programming problems. Iteration means generating a sequence of outcomes. Programmers prefer it to solve a problem where they can find the solution after a few iterations. However, when it comes to solving enormous problems, Recursion plays a vital role in providing a solution in a short time.

Instead of using loops and iterations, Recursion provides sophisticated and straightforward solutions. Using Recursion in programming leads to better strategic thinking and problem-solving techniques. This practice makes the code easy to develop and increases the understandability of the problem.

Formation of Pure Functions

Recursion proves helpful in forming Pure Functions. A pure function refers to a function that returns the value according to the input it receives. Using Recursion, one can simplify problems using pure functions in functional programming, where the user requires solutions to more significant problems.

Time and Space Complexity

A recursive function makes things easier by calling itself without being dependent on another function. Hence, it makes code short, and comprehensible and helps to develop significantly easy algorithms. Moreover, the time complexity of an algorithm is also reduced by it.

Time complexity refers to the total amount of time a program or an algorithm takes to execute. Recursive functions generally produce equal time complexities in comparison to iterative functions. Resultantly, recursive functions complete tasks in a lesser amount of time. However, in some cases, more function calls and returns increase the function’s time complexity significantly.

The space complexity of the recursive function is directly proportional to its depth, i.e., the number of times it has called itself. Furthermore, as the recursive function calls itself repeatedly, the program adds every function on the top of the stack whenever it makes a new call and removes it when the function returns. Therefore, the stack keeps growing, due to which the space complexity of the recursive function is slightly higher or equal to the other functions.

Use of Recursion

Recursion is a very commonly used phenomenon in programming. The programmers use it to find solutions to problems that are breakable into similar smaller problems. For instance, they use it in finding the factorial of a provided input. It is also used in numerous algorithms to find the required solution faster such as binary sort, bubble sort, insertion sort, and selection sort.

Additionally, when it comes to solving problems involving graphs and trees, Recursion functions better as it eliminates the risk of using different iterations to visit every node. A recursive function works better at traversing a tree or graph by providing a specific branch or node needed for a solution.

As the recursive functions consume more memory than others, efficient use of call stack in writing a program is essential. The functions where the call stack works smoothly are considered to be efficient while working with Recursion.

How Recursion Operates

As mentioned above, Recursion breaks down the problem into smaller problems and then solves them individually to form a complete solution. Recursion does its work by keeping the following steps functional.

Base Call

The base call is the part of the function where the function stops after executing it. It is the stop sign for a recursive function to indicate that it has solved the individual problems, and it needs to stop now. If the programmer is not very careful in defining the base case, he may write the infinitely running function, which may crash the program.

Functional Working

Functional working refers to a part of the function where it divides the larger problem into smaller sub-problems that need to be solved.

Recursive Call

Recursive call is an essential part of the function. Here the function calls itself again. However, this time the input is the smaller problem formed in the functional working part.

Example Functions

The following are some basic examples to explain the working of Recursion in coding.

Power Function

The power function takes the two inputs: base and power, and calculates base ^ (power). Before the programmer writes the recursive function, he needs to define the function’s logic cases to understand its proper working.

These are the logic cases for the power function:

• If the power is 0 or less than 0, the function returns 1, called the base condition.
• Otherwise, the function calculates the power using x^y.

Mathematical Definition

The programmers find out the function’s mathematical definition to make the recursive logic of the function. In the cases above, the user decides only to calculate the positive power of the integers. Additionally, the zeroth power of every integer is 1. Moreover, the simple function of calculating the x power of y integer is to multiple y times x. Every time the number is multiplied by itself, the value of x decreases by 1.

Combining the upper cases gives the following mathematical function f(x, y):

f(x, y) = {1 , x<=0 ; y * f(x-1, y) , x>y}

Recursive Algorithm of the Function

In the C++ programming context, the user needs to:

• Declare a function with a name, such as p().
• Define its input parameters and their types, i.e., p (int power, int base)
• Define the return type of the function, i.e., int.

Converting the mathematical function into C++ function gives:

int p(int power , int base)
{
 if (power <= 0) {//base case
  return 1;
 }
 else {
 return base * p(power -1 , base);
 }
}

Dry Run

Input: 2, 2
Working :
 (2 <= 0) false
 Return 2 * p (1, 2)
 (1 <=0) false
 Return 2* p(0,2)
 (0 <=0) true
 Return 1
 Return 2* 1
 Return 2 * 2 * 1
Output: 2*2*1 = 4

Factorial Function

The factorial function is the function that multiplies the number with all its predecessors, and is denoted by ‘!’. E.g. the factorial of 4 can be expressed as 4! = 4 X 3 X 2 X 1. In other words, x! = x * (x-1) * (x-2) * … 2 * 1.

These are the required logic cases to break the factorial problem:

• If the input integer is 0 or 1, the factorial is 1, which is the base case for this function.
• If the input is a positive integer greater than 1, it multiplies the integer with all the numbers below it.

Mathematical Definition

Combining the upper cases gives the following mathematical function f(x):

F(x) = {1 , x=1 or 0 ; x* f(x-1) , x>1}

Recursive Algorithm

To write this function in C++, the user needs to:

• Declare a function with a name, such as factorial ().
• Define its input parameters and their types, i.e., factorial (int number)
• Define the return type of the function, i.e., int.

Converting the mathematical function into C++ gives:

int factorial( int number)
{ 
 if (number == 1) {//base case
  return 1;
 }
 else {
  return number * factorial(number - 1);
 }
}

Dry Run

Input: 3
Working :
 (3 ==1) false
 Return 3 * factorial(2)
 (2 ==1) false
 Return 2* factorial (1)
 (1==1) true
 Return 1
 Return 2 *1
 Return 3 * 2 *1
Output: 3*2*1 = 6

Application: Factorial

Factorial f (x): f(n) = n*f(n-1), the base condition: if n<=1 then f(n) = 1.

As discussed, recursion aims to segregate the problem into smaller equations till the base condition is implementable. For example, the above factorial program, it is resolving the factorial function f(n) by calling a reduced factorial function f(n-1); it frequently happens until the n value reaches base condition(f(1)=1). If the user does not explain the base condition in the recursive function, it may show a stack overflow error.

Memory Allocation

When a user calls a function from main (), the memory is stored in the stack adaptor. The recursive function calls itself. The memory for a called function (storing in a stack) on top of memory allocated to the calling function and various copies of local variables creates for each function call. When it reaches the base condition, the function returns the value to the main function by whom it is getting called, memory is de-allocated, and the course continues.

// A C++ program to demonstrate working of
// recursion
#include <bits/stdc++.h>
using namespace std;

void ExampleFunction(int test)
{
    if (test < 1)
        return;
    else {
        cout << test << " ";
        ExampleFunction(test - 1); // statement 2
        cout << test << " ";
        return;
    }
}

When ExampleFunction(3) is called from main(), memory is allocated to ExampleFunction(3) and a local variable test is initialized to 3, and declarations 1 to 4 are pushed on the stack adaptor. It first prints ‘3’. In statement 2, ExampleFunction(2) is called and memory is allocated to ExampleFunction(2) a local variable test is initialized to 2, and declarations 1 to 4 are pushed in the stack adaptor. Similarly, ExampleFunction(2) calls ExampleFunction(1) and ExampleFunction(1) calls ExampleFunction(0). ExampleFunction(0) runs through if statement and returns to ExampleFunction(1). The remaining statements of ExampleFunction(1) execute and it returns to ExampleFunction(2) and so on. In the output, result values from 3 to 1 are printed and then 1 to 3 are printed.

Direct Recursion vs Indirect Recursion

Direct recursion: When a function calls itself, it is called direct recursion. The above example is a direct recursion example.

Indirect recursion: When a function takes the help of another function called the calling function, this is called indirect recursion. For example, ExampleFunction A calls ExampleFunction B and ExampleFunction B calls ExampleFunction A.

Tailed and Non-tailed Recursion

If the recursive function executes the recursive call at the end of the function, then that recursive function is called a tailed recursive function. Otherwise, the function is called a non-tailed recursive function. The developers prefer tailed recursion because the compiler can optimize these functions by discarding the function’s stack frame when it calls the new function before ending. The compiler can do this because it has executed the whole function, and the recursive statement is the function’s last statement to be executed. Below are examples of tailed and non-tailed recursive functions.

Tailed Recursion

The below function takes an integer and prints its predecessors greater than zero:

void print(int n)
{
    if (n <= 0)
        return;
    cout << " " << n;

    // The last executed statement is recursive call
    print(n - 1);
}

Non-Tailed Recursion

The below function calculates the factorial of the number. The last call in the function seems to be recursive, but the function calls another function and uses its return value to multiply it with the number “n” and then returns the value. Hence, making it a non-tailed recursive function. However, the users can optimize it to convert it into a tailed-recursive function.

int fact( int n)
{
    if (n <= 0)
        return 1;

    return n * fact(n - 1);
}

Recursive Data Structures in C++

The users can use the recursion to define dynamic data structures, for instance, trees and linked lists. It is called structural recursion. These structures are dynamic; therefore, the users can expand to infinite sizes depending on their needs. For instance, as the data grows, the structure storing it grows to make space for it.

Example

Below is an example of a linked link in C++ using the struct data structure. The struct named “node” stores the integer data, and the “next” variable calls the struct itself. It is initially “null”, but the user uses this “next” variable as the pointer to the next node in the chain to form a link list.

struct node
{
  int data;           // some integer data
  struct node *next;  // pointer to another struct node
};

Stack Overflow in Recursion

Base cases are crucial to stop the recursion processes. As in recursion, the recursive function keeps adding the function calls on the top of the stack. The wrong base case or the absence of a base case can result in the infinite running of the function and the overflow of the stack. For instance, the example function below calculates and returns the given number’s factorial using recursion. However, the base case is invalid; therefore, there is no chance of the function ever stopping because the multiple of no number comes up to be ten in the factorial series of multiple. Therefore, there will be stack overflow because the memory will get exhausted, causing the stack overflow error.

int factorial(int num)
{
    // wrong base case
if (num == 10)
        return 1;
    else
        return num*factorial(num-1);
}

Recursive Programming: Disadvantages

The recursive program requires more space than an iterative program as all functions remain in the stack until reaching the base case.

It requires more time as the function calls and returns overhead.

Recursive Programming: Advantages

Recursion provides a clean and simple code and increases its usability. Some problems are characteristically recursive, like tree traversals and the Tower of Hanoi. For such problems, it is favored to write recursive code. Users may write such codes also iteratively with the help of a stack data structure.

Lastly, it is essential to consider that Recursion may work best for one problem but may not be the best solution for the other. Therefore, programmers need to choose carefully, depending on the problem they want to solve. Although the recursive approach provides an elegant and shorter solution in terms of coding, it sometimes can be impractical.