Introduction to C++ | Recursion

C++ Recursion

Recursion is a programming technique where a function calls itself to solve a problem. The key idea in recursion is breaking down a problem into smaller subproblems of the same type. A function that calls itself is known as a recursive function.

What is Recursion?

In C++, recursion allows a function to solve a problem by solving smaller instances of the same problem. The function repeats itself with a modified argument until it reaches a base case, where the recursion stops.

Basic Structure of a Recursive Function

A recursive function typically consists of two parts:

• Base case: This is the stopping condition that terminates the recursion.
• Recursive case: This part calls the function itself with a modified argument to reduce the problem size.

Syntax of Recursion

        return_type function_name(parameters) {
            if (base_case) {
                return some_value;  // Stop condition
            }
            return function_name(modified_parameters);  // Recursive call
        }
                    

Example: Factorial Calculation using Recursion

One of the most common examples of recursion is calculating the factorial of a number. The factorial of a number n, denoted n!, is defined as the product of all positive integers less than or equal to n:

n! = n * (n-1) * (n-2) * ... * 1

For recursion, the factorial of a number can be expressed as:

n! = n * (n-1)!

In the base case, we define 0! = 1.

        #include <iostream>
        using namespace std;
        
        // Recursive function to calculate factorial
        int factorial(int n) {
            if (n <= 1) {
                return 1;  // Base case: factorial of 0 or 1 is 1
            }
            return n * factorial(n - 1);  // Recursive case
        }
        
        int main() {
            int number = 5;
            cout << "Factorial of " << number << " is: " << factorial(number) << endl;
            return 0;
        }
                    

Output

Explanation of Code

In this example, the function factorial() calls itself with a smaller argument (n - 1) until it reaches the base case where n = 1. The recursive calls "unwind" as the base case is reached, and the factorial is calculated by multiplying the values together.

Advantages of Recursion

• Recursion provides a simple and elegant solution to problems that have a recursive structure, such as the factorial calculation, Fibonacci series, tree traversal, etc.
• It reduces the complexity of code for problems that can be broken down into smaller, similar subproblems.

Disadvantages of Recursion

• Recursive functions can be less efficient than iterative solutions because of the overhead of function calls, which may lead to stack overflow if the recursion depth is too large.
• In some cases, recursion may consume more memory due to the function calls being stored in the call stack.

Tail Recursion

In tail recursion, the recursive call is the last operation in the function, making it more efficient in terms of memory. Some compilers can optimize tail recursion to reduce memory usage by reusing the current function's stack frame.

        #include <iostream>
        using namespace std;
        
        // Tail recursive function to calculate factorial
        int factorialTail(int n, int result = 1) {
            if (n <= 1) {
                return result;  // Base case
            }
            return factorialTail(n - 1, n * result);  // Tail recursive call
        }
        
        int main() {
            int number = 5;
            cout << "Factorial of " << number << " is: " << factorialTail(number) << endl;
            return 0;
        }
                    

Output

Pro Tip: