Fibonacci Using Recursion in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci Recursive Call

What is the output of the following C code that prints Fibonacci numbers using recursion?

DSA C

#include <stdio.h>

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

int main() {
    for (int i = 0; i < 6; i++) {
        printf("%d ", fib(i));
    }
    return 0;
}

A 0 1 1 2 3 5

B 1 1 2 3 5 8

C 0 1 2 3 5 8

D 1 2 3 5 8 13

💡 Hint

Remember that fib(0) = 0 and fib(1) = 1 in this code.

The function fib returns 0 for n=0 and 1 for n=1. The loop prints fib(0) to fib(5), which are 0,1,1,2,3,5.

❓ Predict Output

intermediate

Value of fib(4)

What is the value returned by fib(4) in the following recursive Fibonacci function?

DSA C

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

A 2

B 3

C 5

D 4

💡 Hint

Calculate fib(3) + fib(2) to get fib(4).

fib(4) = fib(3) + fib(2) = (2) + (1) = 3.

🔧 Debug

advanced

Identify the error in Fibonacci recursion

What error will the following code produce when compiled and run?

DSA C

#include <stdio.h>

int fib(int n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
    else return fib(n - 1) + fib(n - 3);
}

int main() {
    printf("%d", fib(4));
    return 0;
}

A Output: 5

B Output: 3

C Runtime error: stack overflow

D Compilation error

💡 Hint

Check the recursive calls and their arguments.

The function calls fib(n-3) which can cause negative arguments leading to infinite recursion and stack overflow.

🧠 Conceptual

advanced

Time Complexity of Recursive Fibonacci

What is the time complexity of the naive recursive Fibonacci function fib(n) defined as fib(n) = fib(n-1) + fib(n-2) with base cases fib(0)=0 and fib(1)=1?

A O(log n)

B O(n)

C O(n^2)

D O(2^n)

💡 Hint

Consider how many calls are made for each fib(n).

Each call to fib(n) makes two calls to fib(n-1) and fib(n-2), leading to exponential growth in calls, O(2^n).

🚀 Application

expert

Output of Memoized Fibonacci Calls

Given the following C code implementing Fibonacci with memoization, what is the output printed by the program?

DSA C

#include <stdio.h>

int memo[6] = {0};

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main() {
    for (int i = 0; i < 6; i++) {
        printf("%d ", fib(i));
    }
    return 0;
}

A 0 1 1 2 3 5

B 0 1 2 3 5 8

C 1 1 2 3 5 8

D 1 2 3 5 8 13

💡 Hint

Memoization stores previously computed results to avoid repeated work.

The memo array caches fib values. The output is the same as naive recursion but computed efficiently: 0 1 1 2 3 5.