Day 45: Recursion in C++ – Concept, Examples, and Advantages | Class 11 - BSEB Class 11-12 Computer Science: 100-Day Bilingual Guide with MCQs, Solutions and Questions

Day 45 – Recursion in C++

Class 11 Computer Science

What is Recursion? (Recursion क्या है?)

Recursion in C++ is a process where a function calls itself directly or indirectly to solve a problem. It is particularly useful for solving problems that can be broken into smaller, similar sub-problems.
C++ में Recursion एक प्रक्रिया है जहाँ एक फ़ंक्शन सीधे या अप्रत्यक्ष रूप से स्वयं को कॉल करता है। यह उन समस्याओं को हल करने में सहायक है जिन्हें छोटे और समान उप-समस्याओं में विभाजित किया जा सकता है।

How Does Recursion Work? (Recursion कैसे काम करता है?)

Recursion works by repeatedly breaking a problem into smaller sub-problems. It involves two main components:
Recursion छोटे-छोटे उप-समस्याओं में समस्या को तोड़कर काम करता है। इसमें दो मुख्य घटक होते हैं:

• Base Case (बेस केस): The condition where the recursion stops.
  वह स्थिति जहाँ Recursion रुक जाता है।
• Recursive Case (रेकर्सिव केस): The part where the function calls itself to solve smaller problems.
  वह हिस्सा जहाँ फ़ंक्शन खुद को कॉल करता है छोटे समस्याओं को हल करने के लिए।

Example (उदाहरण):

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

Advantages of Recursion (Recursion के लाभ)

• Simplifies complex problems into smaller sub-problems.
  जटिल समस्याओं को छोटे उप-समस्याओं में बदल देता है।
• Reduces the need for repetitive code.
  बार-बार कोड लिखने की आवश्यकता को कम करता है।
• Useful for problems like factorial, Fibonacci, and tree traversal.
  फैक्टोरियल, फाइबोनैचि, और ट्री ट्रैवर्सल जैसी समस्याओं के लिए उपयोगी।

Disadvantages of Recursion (Recursion के नुकसान)

• Consumes more memory due to function call stack.
  फंक्शन कॉल स्टैक के कारण अधिक मेमोरी उपयोग करता है।
• May lead to stack overflow if the base case is not defined correctly.
  बेस केस सही से परिभाषित न होने पर स्टैक ओवरफ्लो हो सकता है।
• Sometimes slower than iterative solutions.
  कभी-कभी इटरेटिव समाधानों से धीमा होता है।

Examples of Recursion in C++ (C++ में Recursion के उदाहरण)

Example 1: Factorial of a Number

#include <iostream>
using namespace std;

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

int main() {
    int num = 5;
    cout << "Factorial of " << num << " is " << factorial(num);
    return 0;
}

Output:

Factorial of 5 is 120

Example 2: Fibonacci Series

#include <iostream>
using namespace std;

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

int main() {
    int n = 6;
    cout << "Fibonacci series up to " << n << " terms:" << endl;
    for (int i = 0; i < n; i++) {
        cout << fibonacci(i) << " ";
    }
    return 0;
}

Output:

Fibonacci series up to 6 terms:
0 1 1 2 3 5

Practice Questions

Multiple Choice Questions (MCQs)

1. What is recursion in C++?
   (a) Function calling itself | (b) Looping | (c) Memory allocation | (d) None
2. Which part of recursion stops the function from infinite calls?
   (a) Base Case | (b) Recursive Case | (c) Loop | (d) None
3. What will happen if the base case is not defined?
   (a) Infinite recursion | (b) Function executes normally | (c) Error | (d) None
4. Which is an example of recursion?
   (a) Fibonacci Series | (b) Sorting | (c) Memory Management | (d) None
5. What is the result of factorial(3)?
   (a) 3 | (b) 6 | (c) 9 | (d) None
6. Which type of problem is suitable for recursion?
   (a) Problems with repeated subproblems | (b) All problems | (c) Iterative problems only | (d) None
7. What happens in recursion when the base case is reached?
   (a) Function stops calling itself | (b) Loop continues | (c) Error occurs | (d) None
8. What is the main drawback of recursion?
   (a) Consumes more memory | (b) Code reusability | (c) Debugging | (d) None
9. What is the output of the following code?
   

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

   (a) 4 | (b) 12 | (c) 24 | (d) None
10. Which of the following is an example of a base case?
    (a) if (n == 0) return 1; | (b) return n * factorial(n - 1); | (c) for loop | (d) None

Answers to MCQs:

1: (a), 2: (a), 3: (a), 4: (a), 5: (b), 6: (a), 7: (a), 8: (a), 9: (c), 10: (a)

Short Answer Questions

1. What is recursion in C++?
   Answer: Recursion is the process where a function calls itself to solve a problem.
2. Explain the two main parts of recursion.
   Answer: Base Case stops the recursion, and Recursive Case continues the function call.
3. Write the syntax of a recursive function.
   Answer:

    functionName(parameters) {
       if (base_condition)
           return value;
       return functionName(modified_parameters);
   }
   

4. What are the advantages of recursion?
   Answer: Simplifies code for problems like factorials and Fibonacci series.
5. Write a recursive function to find the factorial of a number.
   Answer:

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

Long Answer Questions

1. Explain recursion in detail with an example of finding the Fibonacci series.
2. Discuss the advantages and disadvantages of recursion in programming.
3. Write a recursive function to calculate the power of a number (e.g., base^exponent).