Assignment: Recursion | DSA in C++ - Software Development PDF Download

Multiple Choice Questions (MCQs)

Q.1. What is recursion in computer science?
(a) A data structure
(b) A loop construct
(c) A programming technique
(d) A variable type

Ans. (c)

Q.2. In recursion, what is the base case?
(a) The first case in a function
(b) The final case that stops the recursion
(c) The case with the smallest input size
(d) The case with the largest output

Ans. (b)

Q.3. Which of the following is an advantage of using recursion?
(a) Faster execution time
(b) Easier debugging
(c) Smaller memory usage
(d) Simplicity and elegance in code

Ans. (d)

Q.4. What happens if a recursive function does not have a base case?
(a) The program crashes
(b) It goes into an infinite loop
(c) It returns an incorrect result
(d) The compiler gives an error

Ans. (b)

Q.5. Which data structure is commonly used to implement recursion?
(a) Stack
(b) Queue
(c) Linked list
(d) Array

Ans. (a)

High Order Thinking Questions (HOTS)

Q.1. Write a recursive function in C++ to calculate the factorial of a number.

int factorial(int n) {

   if (n == 0)

      return 1;

   else

      return n * factorial(n - 1);

}

Q.2. Implement a recursive function in C++ to find the nth Fibonacci number.

int fibonacci(int n) {

   if (n <= 1)

      return n;

   else

      return fibonacci(n - 1) + fibonacci(n - 2);

}

Q.3. How can recursion be used to solve the Tower of Hanoi problem? Explain the steps involved.

In the Tower of Hanoi problem, recursion can be used as follows:

• Move n-1 disks from the source peg to the auxiliary peg using the destination peg as the intermediate peg.
• Move the nth disk from the source peg to the destination peg.
• Move the n-1 disks from the auxiliary peg to the destination peg using the source peg as the intermediate peg.

Q.4. Write a recursive function in C++ to find the sum of digits of a given number.

int sumOfDigits(int n) {

   if (n < 10)

      return n;

   else

      return n % 10 + sumOfDigits(n / 10);

}

Q.5. What is tail recursion? How does it differ from regular recursion? Provide an example in C++.

Tail recursion is a special case of recursion where the recursive call is the last operation in the function. Unlike regular recursion, tail recursion allows the compiler to optimize the code and avoid building a stack frame for each recursive call.
Example:

void tailRecursive(int n) {

   if (n > 0) {

      // Perform some operations

      tailRecursive(n - 1);

   }

}

Fill in the Blanks

1. Recursion is a programming technique where a function calls ____________.

Ans. itself

2. Every recursive function must have a ____________ to avoid infinite recursion.

Ans. base case

3. Recursion can be used to solve problems that can be broken down into ____________ subproblems.

Ans. smaller

4. The process of solving a problem by breaking it down into smaller subproblems is known as ____________.

Ans. divide and conquer

5. The ____________ data structure is commonly used in recursive algorithms to store intermediate values.

Ans. stack

True or False

1. Recursion is an alternative to loops in programming. (True/False)

Ans. True

2. Recursive functions are always more efficient than iterative functions. (True/False)

Ans. False

3. The recursive solution is always better than the iterative solution for every problem. (True/False)

Ans. False

4. Recursion uses more memory compared to iteration. (True/False)

Ans. True

5. All iterative solutions can be converted into recursive solutions. (True/False)

Ans. False

Hands-On Questions

Q.1. Write a C++ program to calculate the sum of all numbers from 1 to N using recursion.

#include <iostream>

int sumRecursive(int n) {

   if (n == 0)

      return 0;

   else

      return n + sumRecursive(n - 1);

}

int main() {

   int N;

   std::cout << "Enter a positive integer (N): ";

   std::cin >> N;

   int sum = sumRecursive(N);

   std::cout << "Sum of numbers from 1 to " << N << " = " << sum << std::endl;

   return 0;

}

Q.2. Implement a recursive function in C++ to calculate the power of a number (base^exponent).

#include <iostream>

int powerRecursive(int base, int exponent) {

   if (exponent == 0)

      return 1;

   else

      return base * powerRecursive(base, exponent - 1);

}

int main() {

   int base, exponent;

   std::cout << "Enter base: ";

   std::cin >> base;

   std::cout << "Enter exponent: ";

   std::cin >> exponent;

   int result = powerRecursive(base, exponent);

   std::cout << base << " raised to the power " << exponent << " = " << result << std::endl;

   return 0;

}

Q.3. Write a recursive function in C++ to reverse a string.

#include <iostream>

#include <string>

void reverseString(std::string& str, int start, int end) {

   if (start >= end)

      return;

   else {

      char temp = str[start];

      str[start] = str[end];

      str[end] = temp;

      reverseString(str, start + 1, end - 1);

   }

}

int main() {

   std::string str;

   std::cout << "Enter a string: ";

   std::cin >> str;

   reverseString(str, 0, str.length() - 1);

   std::cout << "Reversed string: " << str << std::endl;

   return 0;

}

Q.4. Create a recursive function in C++ to find the GCD (Greatest Common Divisor) of two numbers.

#include <iostream>

int gcdRecursive(int a, int b) {

   if (b == 0)

      return a;

   else

      return gcdRecursive(b, a % b);

}

int main() {

   int num1, num2;

   std::cout << "Enter two numbers: ";

   std::cin >> num1 >> num2;

   int gcd = gcdRecursive(num1, num2);

   std::cout << "GCD of " << num1 << " and " << num2 << " = " << gcd << std::endl;

   return 0;

}

Q.5. Implement a recursive function in C++ to check if a given string is a palindrome or not.

#include <iostream>

#include <string>

bool isPalindrome(std::string str, int start, int end) {

   if (start >= end)

      return true;

   else if (str[start] != str[end])

      return false;

   else

      return isPalindrome(str, start + 1, end - 1);

}

int main() {

   std::string str;

   std::cout << "Enter a string: ";

   std::cin >> str;

   bool palindrome = isPalindrome(str, 0, str.length() - 1);

   if (palindrome)

      std::cout << "The string is a palindrome." << std::endl;

   else

      std::cout << "The string is not a palindrome." << std::endl;

   return 0;

}