Recursion in C++

What is Recursion in C++?

Recursion is a programming technique where a function calls itself in order to solve a problem. This method breaks down complex problems into smaller, more manageable ones by using repeated function calls.

How Recursion Works

A recursive function must have two parts:

• Base case: The condition under which the recursion ends.
• Recursive case: The part where the function calls itself.

Example: Recursive Function

#include <iostream>
using namespace std;

int sum(int k) {
    if (k > 0) {
        return k + sum(k - 1);
    } else {
        return 0;
    }
}

int main() {
    int result = sum(10);
    cout << result;
    return 0;
}
    

Output:

55
    

In this example, the function sum() keeps calling itself by reducing k until it reaches 0. The recursion ends when k becomes 0, which is the base case.

How It Works Internally

Here’s a breakdown of the function calls:

sum(10) returns 10 + sum(9)
sum(9)  returns 9 + sum(8)
sum(8)  returns 8 + sum(7)
...
sum(1)  returns 1 + sum(0)
sum(0)  returns 0
    

All the return values are then added together as the function calls resolve back up the stack.

Benefits of Recursion

• Makes code cleaner and easier to understand for problems like tree traversal, factorial, Fibonacci, etc.
• Breaks down complex problems into simpler sub-problems.

Drawbacks of Recursion

• Uses more memory because of the call stack.
• Can be slower than iterative solutions for large input sizes.

Recursion vs Iteration

Recursion and iteration can both be used to solve repetitive problems. Iteration uses loops, while recursion uses repeated function calls. Recursion can be more intuitive for problems that have a recursive structure, but iteration is usually more memory-efficient.

Conclusion

Recursion in C++ is a powerful concept that helps solve complex problems with simple logic. By understanding how to implement recursive functions and recognizing when to use them, you can write more elegant and maintainable C++ code.