C++ Functions Recursion

Syntax

Recursion is a technique that allows the function to call itself. A recursive function consists of:

• A base case
• A recursive case

The syntax of a recursive function in C++ is:

return_type function_name(int parameter)
{
    if (base condition)
    {
        // Base case 
    }
    else
    {
        // Recursive case 
        return function_name(modified_parameter);
    }
}

Example

Let's consider a function factorial() that calculates the factorial of a given number using recursion:

#include <iostream>
using namespace std;

int factorial(int n)
{
    if (n == 0)
        return 1;
    else
        return n * factorial(n - 1);
}

int main()
{
    int n = 5;
    cout << "Factorial of " << n << " is " << factorial(n) << endl;
    return 0;
}

Output:

Factorial of 5 is 120

Explanation

The factorial() function calculates the factorial of a given integer n.

Initially, the function is called with n = 5. Since n is not equal to 0, the function executes the recursive case and calls itself with n = 4.

Again, the recursive case is executed with n = 3 and the function calls itself with n = 2. This process continues until the base case is met, when n becomes 0.

At this point, the function returns 1 and the call stack is popped. The previous call to factorial(1) resumes execution and the result is printed on the console.

Thus, the output is "Factorial of 5 is 120".

Use

Recursion is an important concept in programming and can be used to solve many problems. Here are some common use cases:

• Traverse tree data structures, such as binary trees or linked lists.
• Divide a problem into subproblems, solve each subproblem, and combine the results to solve the original problem - this is called divide and conquer.
• Implement mathematical functions, such as the factorial or Fibonacci series, that rely on recursive computations.

Important Points

When using recursion, keep the following in mind:

• The function should have a base case that terminates the recursion.
• Each recursive call should bring you closer to the base case.
• Recursive functions are less efficient than iterative alternatives because of the overhead of creating new function calls on the stack.

Summary

Recursion is a technique for a function to call itself and provides an elegant solution to a wide range of programming problems. When using it, it is essential to consider the base case, recursive case, and performance implications.