The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Recursion

Next ►
►

Recursion is a fundamental concept in computer science and programming where a function calls itself directly or indirectly to solve a problem. It is a powerful tool for solving problems that can be broken down into smaller, similar sub-problems. In this section, we will explore the basics of recursion, understand how it works, and see practical examples in C++.

Key Concepts

  1. Base Case: The condition under which the recursive function stops calling itself. It prevents infinite recursion and eventually terminates the function.
  2. Recursive Case: The part of the function where the function calls itself with a modified argument, moving towards the base case.
  3. Stack Overflow: A potential issue where too many recursive calls exhaust the stack memory, leading to a program crash.

How Recursion Works

When a recursive function is called, the current state of the function (including its variables and execution point) is saved on the call stack. The function then calls itself with new arguments. This process continues until the base case is met. Once the base case is reached, the function starts returning and the saved states are popped off the stack one by one.

Example: Factorial Calculation

The factorial of a non-negative integer \( n \) (denoted as \( n! \)) is the product of all positive integers less than or equal to \( n \). The factorial can be defined recursively as:

  • \( 0! = 1 \) (Base Case)
  • \( n! = n \times (n-1)! \) (Recursive Case)

Code Example

#include <iostream>
using namespace std;

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

int main() {
    int number;
    cout << "Enter a positive integer: ";
    cin >> number;
    
    if (number < 0) {
        cout << "Factorial is not defined for negative numbers." << endl;
    } else {
        cout << "Factorial of " << number << " is " << factorial(number) << endl;
    }
    
    return 0;
}

Explanation

  1. Base Case: When n is 0, the function returns 1.
  2. Recursive Case: When n is greater than 0, the function calls itself with n-1 and multiplies the result by n.

Practical Exercises

Exercise 1: Fibonacci Sequence

Write a recursive function to calculate the \( n \)-th Fibonacci number. The Fibonacci sequence is defined as:

  • \( F(0) = 0 \)
  • \( F(1) = 1 \)
  • \( F(n) = F(n-1) + F(n-2) \) for \( n > 1 \)

Solution

#include <iostream>
using namespace std;

// Function to calculate Fibonacci number using recursion
int fibonacci(int n) {
    if (n == 0) { // Base case
        return 0;
    } else if (n == 1) { // Base case
        return 1;
    } else { // Recursive case
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main() {
    int number;
    cout << "Enter a positive integer: ";
    cin >> number;
    
    if (number < 0) {
        cout << "Fibonacci is not defined for negative numbers." << endl;
    } else {
        cout << "Fibonacci number at position " << number << " is " << fibonacci(number) << endl;
    }
    
    return 0;
}

Exercise 2: Sum of Digits

Write a recursive function to find the sum of digits of a given positive integer.

Solution

#include <iostream>
using namespace std;

// Function to calculate sum of digits using recursion
int sumOfDigits(int n) {
    if (n == 0) { // Base case
        return 0;
    } else { // Recursive case
        return n % 10 + sumOfDigits(n / 10);
    }
}

int main() {
    int number;
    cout << "Enter a positive integer: ";
    cin >> number;
    
    if (number < 0) {
        cout << "Sum of digits is not defined for negative numbers." << endl;
    } else {
        cout << "Sum of digits of " << number << " is " << sumOfDigits(number) << endl;
    }
    
    return 0;
}

Common Mistakes and Tips

  • Infinite Recursion: Ensure that the base case is correctly defined and reachable to prevent infinite recursion.
  • Stack Overflow: Be cautious with deep recursion as it can lead to stack overflow. Consider using iterative solutions for problems with large input sizes.
  • Debugging: Use print statements to trace the function calls and understand the flow of recursion.

Conclusion

Recursion is a powerful technique for solving problems that can be broken down into smaller, similar sub-problems. Understanding the base case and recursive case is crucial for writing correct recursive functions. Practice with different problems to get comfortable with recursion and recognize when it is an appropriate solution. In the next module, we will delve into arrays and strings, which are fundamental data structures in C++.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2024. All rights reserved