Recursion Basic

Recursion is a technique in which a function calls itself either directly or indirectly in order to solve a problem. It breaks down complex problems into smaller, simpler subproblems. A recursive function has two parts:

Base Case: The condition under which the recursion terminates.
Recursive Case: The part of the function that reduces the problem into smaller instances and makes a recursive call.

How Recursion Works:

Recursion works by the function calling itself with modified parameters until the base case is met. Each recursive call creates a new instance of the function, and the calls are stored on the call stack. Once the base case is reached, the function starts returning and unwinding the stack, resolving each call step by step.

Syntax:

returnType functionName(parameters) {
    // Base case to stop recursion
    if (base_condition) {
        return some_value;
    }
    // Recursive case
    return functionName(modified_parameters);
}

Example 1: Factorial Using Recursion

Problem: Calculate the factorial of a given number n.

Formula: n!=n×(n−1)!, where 0!=1.

#include <iostream>
using namespace std;

int factorial(int n) {
    // Base case: if n is 0, return 1
    if (n == 0) {
        return 1;
    }
    // Recursive case: n * factorial(n - 1)
    return n * factorial(n - 1);
}
int main() {
    int number = 5;
    cout << "Factorial of " << number << " is " << factorial(number) << endl;
    return 0;
}

Explanation:

Base Case: When n=0, the function returns 1 because the factorial of 0 is defined as 1.
Recursive Case: The function calls itself with n−1, gradually reducing the value of n until the base case is met.

Call Stack for factorial(5):

factorial(5) → 5 * factorial(4)
factorial(4) → 4 * factorial(3)
factorial(3) → 3 * factorial(2)
factorial(2) → 2 * factorial(1)
factorial(1) → 1 * factorial(0)
factorial(0) → returns 1 (base case)
Now each call returns and multiplies:
- factorial(1) returns 1,
- factorial(2) returns 2,
- factorial(3) returns 6,
- factorial(4) returns 24,
- factorial(5) returns 120.

Example 2: Fibonacci Series Using Recursion

Problem: Calculate the nth Fibonacci number.
Fibonacci Series: F(n)=F(n−1)+F(n−2), where F(0)=0 and F(1)=1.

#include <iostream>
using namespace std;

int fibonacci(int n) {
    // Base case: F(0) = 0, F(1) = 1
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    // Recursive case: F(n) = F(n-1) + F(n-2)
    return fibonacci(n - 1) + fibonacci(n - 2);
}

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

Explanation:

Base Case: When n=0, return 0; when n=1, return 1.
Recursive Case: For any n≥2, the function calls itself for the two previous Fibonacci numbers F(n−1) and F(n−2).

Recursion vs Iteration:

Recursion: The function calls itself to solve a smaller subproblem. It uses a call stack and can be less memory-efficient for large problems.
Iteration: Uses loops to repeat operations without the overhead of function calls. Iterative solutions are often more space-efficient but can be less elegant for certain problems (like tree traversal).

Advantages of Recursion:

Simpler Code: Recursion often leads to shorter and more readable code, especially for problems like tree traversal, factorial, or Fibonacci sequences.
Divides Complex Problems: Problems are broken down into smaller subproblems, making the logic clearer.

Disadvantages of Recursion:

Memory Overhead: Each recursive call uses stack space, and large recursive depths can cause stack overflow.
Efficiency: Recursion can lead to repeated calculations, as seen in the Fibonacci example. This can often be mitigated using memoization.

Tail Recursion:

Tail recursion is a special form of recursion where the recursive call is the last operation in the function. In such cases, the compiler can optimize the recursion to avoid adding a new frame to the stack, making it more efficient.

#include <iostream>
using namespace std;

int tailRecursiveFactorial(int n, int result = 1) {
    // Base case: if n is 0, return result
    if (n == 0) {
        return result;
    }
    // Recursive case: pass the updated result
    return tailRecursiveFactorial(n - 1, result * n);
}

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

Memoization:

Memoization is a technique used to optimize recursive functions by storing previously calculated results. It prevents recalculating values, significantly improving performance for problems like the Fibonacci sequence.

Example (Fibonacci with Memoization):

#include <iostream>
#include <vector>
using namespace std;

vector<int> memo(100, -1);  // Initialize a memoization array with -1

int fibonacci(int n) {
    // Base case
    if (n == 0) return 0;
    if (n == 1) return 1;

    // Check if result is already calculated
    if (memo[n] != -1) return memo[n];

    // Store the result in memo array
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2);

    return memo[n];
}

int main() {
    int n = 10;
    cout << "Fibonacci of " << n << " is " << fibonacci(n) << endl;
    return 0;
}