CHASH Tutorial

Recursion in C++

Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem until it reaches a base case (stopping condition). It is useful for problems that can be broken down into simpler, repetitive tasks.

1. How Recursion Works

When a recursive function is called:

• The function checks if the base case is met. If yes, it stops calling itself.
• If not, it calls itself with modified arguments that move towards the base case.
• Each recursive call adds a new layer on the call stack.
• When the base case is reached, the calls start returning back in reverse order, resolving each call.

2. Anatomy of a Recursive Function

A recursive function must have:

• Base Case: Condition to stop recursion.
• Recursive Case: Part where the function calls itself with new arguments.

3. Example: Factorial Calculation

The factorial of a non-negative integer n (written as n!) is the product of all positive integers less than or equal to n.

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

Here, when n becomes 0, recursion stops. Otherwise, the function calls itself with n - 1.

4. Example: Fibonacci Series

The Fibonacci sequence is a series where each number is the sum of the two preceding ones, starting from 0 and 1.

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

The function calls itself twice to get the two previous Fibonacci numbers and sums them.

5. Visualizing Recursion

For factorial(3), the call stack grows as follows:

• factorial(3) calls factorial(2)
• factorial(2) calls factorial(1)
• factorial(1) calls factorial(0)
• factorial(0) returns 1 (base case)
• factorial(1) returns 1 * 1 = 1
• factorial(2) returns 2 * 1 = 2
• factorial(3) returns 3 * 2 = 6

6. Advantages and Disadvantages of Recursion

• Advantages:
  • Simple and clean code for complex problems.
  • Ideal for divide-and-conquer algorithms.
• Disadvantages:
  • Uses more memory because of multiple function calls on the call stack.
  • Can cause stack overflow if recursion depth is too deep.
  • Sometimes less efficient than iterative solutions.

7. Tips for Writing Recursive Functions

• Always define a clear base case.
• Ensure each recursive call works towards the base case.
• Test with simple input to verify correctness.
• Consider using iteration if recursion depth becomes very large.

Example Program: Calculating Factorial Recursively

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n == 0)
        return 1;  // Base case
    else
        return n * factorial(n - 1);  // Recursive call
}

int main() {
    int num;
    cout << "Enter a positive integer: ";
    cin >> num;

    if (num < 0)
        cout << "Factorial is not defined for negative numbers." << endl;
    else
        cout << "Factorial of " << num << " is " << factorial(num) << endl;

    return 0;
}