Prev Next

C++ Recursion

Recursion is a programming technique where a function calls itself to solve a problem. It is often used to solve problems that can be broken down into smaller, similar subproblems.

Key Topics

1. Basic Concept of Recursion

A recursive function typically has two main components: the base case and the recursive case. The base case stops the recursion, while the recursive case continues to call the function with modified arguments.

Example: Simple Recursive Function

void printNumbers(int n) {
    if (n > 0) {
        printNumbers(n - 1);
        std::cout << n << " ";
    }
}

Output:

1 2 3 4 5

Code Explanation: This function prints numbers from 1 to n. The base case is when n is not greater than 0. The recursive case calls printNumbers with n - 1 before printing n.

2. Factorial Example

The factorial of a number n is the product of all positive integers less than or equal to n. It can be defined recursively as follows:

Example: Factorial Function

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

Output:

120 (for factorial(5))

Code Explanation: This function calculates the factorial of n. The base case returns 1 when n is less than or equal to 1. The recursive case multiplies n by the factorial of n - 1.

3. Fibonacci Example

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. It can also be defined recursively.

Example: Fibonacci Function

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Output:

5 (for fibonacci(5))

Code Explanation: This function computes the nth Fibonacci number. The base case returns n when n is 0 or 1. The recursive case sums the results of the Fibonacci function called with n - 1 and n - 2.

Best Practices

  • Always define a base case to prevent infinite recursion.
  • Be cautious of stack overflow errors with deep recursion.
  • Consider using iterative solutions for performance-critical applications.

Key Takeaways

  • Recursion is a powerful tool for solving problems that can be divided into smaller subproblems.
  • Understanding the base and recursive cases is crucial for implementing recursive functions.
  • Recursive solutions can be elegant but may not always be the most efficient.
Prev Next