C Program for Fibonacci Using Recursion

A C program for Fibonacci using recursion defines a function like int fibonacci(int n) { if (n <= 1) return n; else return fibonacci(n-1) + fibonacci(n-2); } and calls it to print Fibonacci numbers.

Examples

Input5

OutputFibonacci number at position 5 is 5

Input0

OutputFibonacci number at position 0 is 0

Input10

OutputFibonacci number at position 10 is 55

How to Think About It

To find the Fibonacci number at position n, check if n is 0 or 1 and return n directly. Otherwise, find the sum of Fibonacci numbers at positions n-1 and n-2 by calling the function recursively.

Algorithm

1

Get the input number n.

2

If n is 0 or 1, return n as the Fibonacci number.

3

Otherwise, call the function recursively for n-1 and n-2.

4

Add the results of the two recursive calls.

5

Return the sum as the Fibonacci number at position n.

Code

c

#include <stdio.h>

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

int main() {
    int n = 5;
    printf("Fibonacci number at position %d is %d\n", n, fibonacci(n));
    return 0;
}

Output

Fibonacci number at position 5 is 5

Dry Run

Let's trace fibonacci(5) through the code

1

Call fibonacci(5)

Since 5 > 1, call fibonacci(4) + fibonacci(3)

2

Call fibonacci(4)

Since 4 > 1, call fibonacci(3) + fibonacci(2)

3

Call fibonacci(3)

Since 3 > 1, call fibonacci(2) + fibonacci(1)

4

Call fibonacci(2)

Since 2 > 1, call fibonacci(1) + fibonacci(0)

5

Call fibonacci(1) and fibonacci(0)

Return 1 and 0 respectively

6

Calculate fibonacci(2)

1 + 0 = 1

7

Calculate fibonacci(3)

fibonacci(2) + fibonacci(1) = 1 + 1 = 2

8

Calculate fibonacci(4)

fibonacci(3) + fibonacci(2) = 2 + 1 = 3

9

Calculate fibonacci(5)

fibonacci(4) + fibonacci(3) = 3 + 2 = 5

Function Call	Returned Value
fibonacci(1)	1
fibonacci(0)	0
fibonacci(2)	1
fibonacci(3)	2
fibonacci(4)	3
fibonacci(5)	5

Why This Works

Step 1: Base Case

The function returns n directly when n is 0 or 1 to stop recursion and provide known Fibonacci values.

Step 2: Recursive Calls

For other values, the function calls itself for n-1 and n-2 to build the Fibonacci sequence from smaller problems.

Step 3: Combining Results

The sum of the two recursive calls gives the Fibonacci number at position n, following the sequence definition.

Alternative Approaches

Iterative approach

c

#include <stdio.h>

int fibonacci(int n) {
    int a = 0, b = 1, c, i;
    if (n == 0) return 0;
    for (i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int main() {
    int n = 5;
    printf("Fibonacci number at position %d is %d\n", n, fibonacci(n));
    return 0;
}

This uses a loop instead of recursion, which is faster and uses less memory.

Memoization (top-down dynamic programming)

c

#include <stdio.h>

int memo[100] = {0};

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

int main() {
    int n = 5;
    printf("Fibonacci number at position %d is %d\n", n, fibonacci(n));
    return 0;
}

This caches results to avoid repeated calculations, improving performance over plain recursion.

Complexity: O(2^n) time, O(n) space

Time Complexity

The recursive approach calls fibonacci twice for each n > 1, leading to exponential growth in calls, so time is O(2^n).

Space Complexity

The maximum depth of recursion is n, so space complexity is O(n) due to the call stack.

Which Approach is Fastest?

Iterative and memoized methods run in O(n) time and use O(1) or O(n) space, making them faster and more efficient than plain recursion.

Approach	Time	Space	Best For
Recursive	O(2^n)	O(n)	Simple code, small n
Iterative	O(n)	O(1)	Efficiency and large n
Memoization	O(n)	O(n)	Avoid repeated work, moderate complexity