Recursion

Recursion in C++ is a programming technique where a function calls itself repeatedly to solve a problem. It is commonly used for tasks that can be divided into smaller subproblems.

What is Recursion?

Recursion is a process in which a function calls itself until a specific condition is met.

A recursive function has two important parts:

• Base Case → Stops the recursion
• Recursive Call → Function calls itself

Why Use Recursion?

Recursion is useful because it:

• Simplifies complex problems
• Reduces code length
• Works well with hierarchical data
• Is commonly used in algorithms and data structures

Syntax of Recursive Function

return_type function_name(parameters) {

    if (base_condition) {
        return value;
    }

    return function_name(smaller_problem);
}

Example of Recursion

#include <iostream>
using namespace std;

void countDown(int n) {

    if (n == 0) {
        return;
    }

    cout << n << endl;

    countDown(n - 1);
}

int main() {
    countDown(5);

    return 0;
}

Output

5
4
3
2
1

How Recursion Works

1. Function is called
2. Function performs a task
3. Function calls itself with smaller input
4. Process repeats
5. Base case stops recursion

Example: Factorial Using Recursion

Factorial formula:

$n! = n \times (n-1)!$n!=n×(n−1)!

#include <iostream>
using namespace std;

int factorial(int n) {

    if (n == 0 || n == 1) {
        return 1;
    }

    return n * factorial(n - 1);
}

int main() {
    cout << factorial(5);

    return 0;
}

Output

120

Example: Fibonacci Series Using Recursion

#include <iostream>
using namespace std;

int fibonacci(int n) {

    if (n == 0) {
        return 0;
    }

    if (n == 1) {
        return 1;
    }

    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    cout << fibonacci(6);

    return 0;
}

Advantages of Recursion

• Makes code shorter
• Solves complex problems easily
• Useful for tree and graph structures
• Improves code readability in some cases

Disadvantages of Recursion

• Can use more memory
• May be slower than loops
• Incorrect base case can cause infinite recursion

Why Recursion is Important

Recursion is important because it:

• Helps solve divide-and-conquer problems
• Is widely used in algorithms
• Supports advanced data structures
• Simplifies repetitive problem-solving

Real-Life Example

Think of standing between two mirrors:

• One reflection creates another reflection repeatedly
• The process continues until it fades away

This is similar to recursion where a function keeps calling itself.

Conclusion

Recursion in C++ is a powerful programming technique where a function calls itself to solve smaller versions of a problem. It is widely used in algorithms, mathematical calculations, and advanced programming concepts.