← Back to Lab HomeLab Exercise – 09

Experiment 9 – Fibonacci Using Recursion

Aim

To generate Fibonacci series using recursive functions in C programming. The Fibonacci sequence is defined as: F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1. This experiment helps students understand recursion, base cases, recursive problem decomposition, and the trade-offs between recursive and iterative solutions.

Through this experiment, students will learn to identify base cases, design recursive solutions, understand the call stack, and recognize when recursion is appropriate versus when iterative solutions are more efficient.

Learning Outcomes

After completing this experiment, students will be able to:

  • Understand the concept of recursion and recursive function calls
  • Identify and implement base cases for recursive functions
  • Design recursive solutions for mathematical problems
  • Understand the Fibonacci sequence and its recursive definition
  • Trace recursive function execution and understand the call stack
  • Recognize the exponential time complexity of naive recursive Fibonacci
  • Compare recursive and iterative approaches
  • Understand when recursion is appropriate and when to avoid it

Algorithm

The recursive algorithm for Fibonacci follows the mathematical definition directly:

Recursive Fibonacci Algorithm:

  1. Base Case 1: If n == 0, return 0
  2. Base Case 2: If n == 1, return 1
  3. Recursive Case: If n > 1, return fibonacci(n-1) + fibonacci(n-2)

Note: This recursive approach has exponential time complexity O(2^n) because it recalculates the same values multiple times. For better performance with large n, use iterative approach (O(n)) or memoization (O(n) with O(n) space).

Procedure

  1. Include stdio.h header file
  2. Define a recursive function fibonacci(int n):
    • Base case 1: If n == 0, return 0
    • Base case 2: If n == 1, return 1
    • Recursive case: Return fibonacci(n-1) + fibonacci(n-2)
  3. In main function, read the number of terms from user
  4. Use a loop to call fibonacci function for each term (0 to n-1)
  5. Display each Fibonacci number
  6. Note: Recursive approach is less efficient than iterative for large n

Flowchart

Function: fibonacci(n)
  START
    │
    ├─→ IF (n == 0)
    │   │
    │   └─→ RETURN 0
    │
    ├─→ IF (n == 1)
    │   │
    │   └─→ RETURN 1
    │
    ├─→ ELSE
    │   │
    │   └─→ RETURN fibonacci(n-1) + fibonacci(n-2)
    │
  END

Main Function:
  START
    ├─→ Read n (number of terms)
    ├─→ FOR i = 0 to n-1
    │   │
    │   └─→ Display fibonacci(i)
    │
    └─→ END

Program Code

#include <stdio.h>

// Recursive function to calculate nth Fibonacci number
int fibonacci(int n) {
    // Base cases
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    
    // Recursive case
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n, i;
    
    // Input number of terms
    printf("Enter the number of terms: ");
    scanf("%d", &n);
    
    if (n < 0) {
        printf("Error! Number of terms cannot be negative.\n");
        return 1;
    }
    
    // Display Fibonacci series
    printf("\nFibonacci Series (first %d terms):\n", n);
    for (i = 0; i < n; i++) {
        printf("%d ", fibonacci(i));
    }
    printf("\n");
    
    // Display nth Fibonacci number
    if (n > 0) {
        printf("\nThe %d", n);
        if (n == 1) {
            printf("st");
        } else if (n == 2) {
            printf("nd");
        } else if (n == 3) {
            printf("rd");
        } else {
            printf("th");
        }
        printf(" Fibonacci number is: %d\n", fibonacci(n - 1));
    }
    
    return 0;
}

// Note: For better performance with large n, use iterative approach:
/*
int fib_iterative(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}
*/

Sample Input and Output

Sample 1:

Input:

Enter the number of terms: 10

Output:

Fibonacci Series (first 10 terms):
0 1 1 2 3 5 8 13 21 34 

The 10th Fibonacci number is: 34

Sample 2:

Input:

Enter the number of terms: 7

Output:

Fibonacci Series (first 7 terms):
0 1 1 2 3 5 8 

The 7th Fibonacci number is: 8

Sample 3:

Input:

Enter the number of terms: 1

Output:

Fibonacci Series (first 1 terms):
0 

The 1st Fibonacci number is: 0

Use Case / Real-world Relevance

Recursion and Fibonacci numbers have important applications:

  • Algorithm Design: Many algorithms use recursion (tree traversal, divide-and-conquer, backtracking)
  • Data Structures: Tree and graph operations are naturally recursive
  • Mathematical Modeling: Fibonacci appears in nature (spiral patterns, golden ratio)
  • Financial Analysis: Fibonacci retracements used in technical analysis of stock markets
  • Computer Graphics: Generating natural-looking curves and patterns
  • Dynamic Programming: Understanding memoization and optimization of recursive solutions
  • Compiler Design: Recursive descent parsing, expression evaluation
  • Problem Solving: Breaking complex problems into smaller subproblems

Understanding recursion is crucial for advanced programming. While recursive solutions are often elegant, they require careful design of base cases and can be optimized with techniques like memoization. Recursion is fundamental to many algorithms including tree traversal, divide-and-conquer, and dynamic programming.

Viva Questions

Q1: What is recursion and what are its essential components?

Recursion is a technique where a function calls itself to solve a problem. Essential components: base case(s) that stop recursion (prevent infinite calls), recursive case that calls the function with smaller/ simpler input, and progress toward base case. Without proper base cases, recursion leads to infinite loops and stack overflow.

Q2: Why is the recursive Fibonacci inefficient for large n?

Recursive Fibonacci recalculates the same values many times. For example, fibonacci(5) calls fibonacci(3) twice, fibonacci(2) three times, etc. This leads to exponential time complexity O(2^n). For n=40, this means over 1 billion function calls! Iterative approach calculates each value once, giving O(n) time complexity.

Q3: What is the call stack and how does it relate to recursion?

Call stack stores function call information (parameters, local variables, return address). Each recursive call pushes a new frame onto the stack. When base case is reached, frames are popped in reverse order. Deep recursion can cause stack overflow if stack size is exceeded. Each recursive call uses stack space until it returns.

Q4: How can we optimize recursive Fibonacci?

Use memoization: store previously calculated values in an array. Before calculating, check if value exists. If yes, return it; if no, calculate and store. This reduces time complexity from O(2^n) to O(n) with O(n) space. Alternatively, use iterative approach which is O(n) time and O(1) space, or use matrix exponentiation for O(log n) time.

Q5: When should we use recursion vs iteration?

Use recursion for problems with natural recursive structure (trees, divide-and-conquer, backtracking) or when recursive solution is more intuitive. Use iteration when recursion causes performance issues, stack overflow risk, or when iterative solution is simpler. Many recursive problems can be converted to iterative using stacks or loops.

Q6: What happens if we forget base cases in recursive Fibonacci?

Without base cases, the function will call itself indefinitely: fibonacci(n) calls fibonacci(n-1) and fibonacci(n-2), which call more functions, never stopping. This causes infinite recursion, leading to stack overflow (running out of stack space) and program crash. Base cases are essential to stop recursion.

Q7: Can you trace the execution of fibonacci(4)?

fibonacci(4) calls fibonacci(3) + fibonacci(2). fibonacci(3) calls fibonacci(2) + fibonacci(1). fibonacci(2) calls fibonacci(1) + fibonacci(0). Base cases: fibonacci(1)=1, fibonacci(0)=0. So fibonacci(2)=1+0=1, fibonacci(3)=1+1=2, fibonacci(4)=2+1=3. The call tree shows many repeated calculations, demonstrating inefficiency.

Q8: What is tail recursion and can Fibonacci be tail-recursive?

Tail recursion occurs when the recursive call is the last operation. Standard Fibonacci isn't tail-recursive because it performs addition after recursive calls. However, we can write tail-recursive version using accumulator parameters. Tail recursion can be optimized by compilers to avoid stack growth, but C doesn't guarantee this optimization. Iterative version is clearer for Fibonacci.

Related Links

🔹 Author: Dr. J. Siva Ramakrishna

🔹 Institution: Narayana Engineering College, Gudur

🔹 Last Updated: 9 January 2026

← Previous: Experiment 8Next: Experiment 10→