The following questions are based on what we have learned so far in Chapter 12 – Recursion in C. To test your understanding, try answering the following questions. The explanations are also provided to each question so you can always check the correctness of your answers. All the best 👍
What is the base case in a recursive function?
The base case is the condition responsible to terminate the recursion. It prevents infinite function calls.
Which of the following is true about recursion?
Tail recursion can be optimized by compilers through tail call optimization, making it as efficient as the iteration.
What will be the output of the following code?
#include <stdio.h>
int fib(int n) {
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
int main() {
printf("%d", fib(5));
}The recursive Fibonacci function calculates the 5th Fibonacci number which is 5.
Match the following:
Direct recursion occurs when a function calls itself directly, indirect recursion happens when a function calls another function which in turn calls the original function, a tail recursive program is a recursion in which the last operation is the recursive call, and base case refers to a condition where recursion stops.
Which of the following errors would occur if recursion has no base case?
Without a base case, recursion would continue indefinitely, eventually causing a stack overflow as each function call takes up stack space.
What will be the output of the following code?
#include <stdio.h>
int foo(int n) {
if (n == 1)
return 1;
else
return 2 * foo(n - 1);
}
int main() {
printf("%d", foo(3));
}foo(3) calls foo(2) which calls foo(1). As n is 1, the base case is satisfied and hence value 1 will be returned to the caller which is foo(2). Value 2 is multiplied to 1, and the result is 2. This value is returned to foo(3) in which 2 is multiplied to 2 which is returned to the main function where the printf function will print the result which 4.
On a Fibonacci recursive function, how many times is fib(2) called while computing fib(5)?
In fib(5), fib(2) is called three times, once in fib(4) and twice in fib(3).
Which of the following recursion types calls itself directly?
Direct recursion refers to a function that calls itself directly.
What will be the output of the following code?
#include <stdio.h>
void recur(int n)
{
if (n <= 0)
return;
printf("%d ", n);
recur(n-2);
printf("%d ", n);
}
int main() {
recur(5);
}Initially, the recur() function is called with value 5. The first printf is invoked which prints the value 5 on the screen. Then, recur() is called once again, but this time the value of n is 3. Value 3 will be printed by the first printf call and in the same way value 1 is also displayed. At this point, the output is 5 3 1, but this doesn’t come to an end yet. After recur(n-2), we have a printf function which will display values starting from 1. Then, the function returns to the caller of recur(1) which is recur(3). Here the value of n is 3, so 3 will be displayed, and in the same way, value 5 will be displayed. Therefore, the final output is 5 3 1 1 3 5.
Fill in the blanks:
A non-tail recursive function typically requires _____ after the recursive call is made.
Non-Tail recursive functions need to perform additional operations before returning to the caller.
Your score is out of
Leave a comment