Fibonacci Using Recursion: flowchart, algorithm and program

This program reads n and prints the nth Fibonacci number using a function fib(n) that calls itself. Each number is the sum of the two before it, so fib(n) is built from fib(n - 1) and fib(n - 2), and the recursion stops at fib(0) = 0 and fib(1) = 1.

▶ Watch the dry run step by step →

Algorithm

  1. Step 1: Start.
  2. Step 2: Read n.
  3. Step 3: Call fib(n).
  4. Step 4: If n == 0, go to step 5; otherwise go to step 6.
  5. Step 5: Set result = 0. Go to step 9.
  6. Step 6: If n == 1, go to step 7; otherwise go to step 8.
  7. Step 7: Set result = 1. Go to step 9.
  8. Step 8: Set result = fib(n-1) + fib(n-2).
  9. Step 9: Print n and result.
  10. Step 10: Stop.

Program in C, Python and Java

Fibonacci Using Recursion program in C

#include <stdio.h>

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

int main() {
    int n;
    printf("Enter n: ");
    scanf("%d", &n);
    printf("Fibonacci number at position %d is %d\n", n, fib(n));
    return 0;
}

Fibonacci Using Recursion program in Python

def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

n = int(input("Enter n: "))
print("Fibonacci number at position", n, "is", fib(n))

Fibonacci Using Recursion program in Java

import java.util.Scanner;

public class Main {
    static int fib(int n) {
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter n: ");
        int n = sc.nextInt();
        System.out.println("Fibonacci number at position " + n + " is " + fib(n));
    }
}

Sample input: n = 4
Output: Enter n: Fibonacci number at position 4 is 3

How it works

  • The two base cases come first: if n == 0 return 0, and if n == 1 return 1. These stop the recursion.
  • For any larger n, the function returns fib(n - 1) + fib(n - 2). Each of those calls works on a smaller number, so it moves toward a base case.
  • For n = 4: fib(4) = fib(3) + fib(2). fib(3) = fib(2) + fib(1), and fib(2) = fib(1) + fib(0) = 1 + 0 = 1.
  • So fib(3) = 1 + 1 = 2, and fib(4) = 2 + fib(2) = 2 + 1 = 3. That is the value printed.
  • main() only reads n with scanf, calls fib(n) once, and prints the result. All the work happens inside the recursive calls.

Dry run (trace table)

StepLineBoxnresultOutput
111Start
214Read n4
315Call fib(n)4
44n == 0?4
56n == 1?4
64n == 0?3
76n == 1?3
84n == 0?2
96n == 1?2
104n == 0?1
116n == 1?1
127result = 111
134n == 0?0
145result = 000
158result = fib(n-1) + fib(n-2)21
164n == 0?1
176n == 1?1
187result = 111
198result = fib(n-1) + fib(n-2)32
204n == 0?2

Time and space complexity

Time: O(2^n) · Space: O(n). Each call branches into two recursive calls, giving about 2^n calls, while the recursion stack goes at most n levels deep.

Common mistakes

  • Leaving out a base case (especially n == 1). The calls then go below 0 and never stop, which ends in a stack overflow.
  • Writing fib(n - 1) + fib(n - 1) or fib(n) + fib(n - 1) instead of fib(n - 1) + fib(n - 2).
  • Assuming the sequence starts at 1, 1. Here fib(0) = 0 and fib(1) = 1, so fib(4) is 3, not 5.
  • Using a large n like 40 or 50. This version recomputes the same values many times, so it becomes very slow.

Viva questions

Q1. What are the base cases in your fib function, and why do you need them?

fib(0) returns 0 and fib(1) returns 1. Without them the recursion would never stop and the program would crash with a stack overflow.

Q2. Trace fib(4). How many times is fib(2) called?

fib(4) calls fib(3) and fib(2); fib(3) calls fib(2) and fib(1). So fib(2) is called twice, and each call expands again into fib(1) and fib(0).

Q3. What happens if the user enters a negative number, for example -3?

Neither base case matches, so fib(-3) calls fib(-4) and fib(-5), going further from the base cases forever. This leads to infinite recursion and a stack overflow. The fix is to check n < 0 first and reject it.

Q4. Why is line 8 written as fib(n - 1) + fib(n - 2)? What does it represent?

Each Fibonacci number is the sum of the two before it, so the function calls itself for those two smaller positions and adds the results. Each call moves closer to a base case.

Q5. What is the time complexity of this program, and why is it so slow for large n?

It is exponential, roughly O(2^n), because each call makes two more calls and the same subproblems are recomputed many times. The space used is O(n) for the recursion depth.

Q6. What would change if you wanted to make this faster?

Store results already computed (memoization or dynamic programming) or use a simple loop with two variables. This brings the time down to O(n) because each value is computed only once.

Q7. Why does the program give a wrong answer for something like n = 50, even if you wait long enough?

The return type is int, which is usually 32 bits, so Fibonacci values above 2,147,483,647 (from fib(47) onward) overflow. Using long long or unsigned long long would allow larger n.

Q8. What is the difference between recursion and iteration, and which does this program use?

Recursion solves a problem by having a function call itself on a smaller input until a base case is reached; iteration repeats using a loop. This program uses recursion, and each call uses a new stack frame.

Frequently asked questions

What is the Fibonacci number at position 4 with recursion?

It is 3. The sequence is 0, 1, 1, 2, 3, so fib(4) = fib(3) + fib(2) = 2 + 1 = 3.

Why is recursive Fibonacci slow for large n?

It recalculates the same values again and again. For example, fib(2) is computed several times inside fib(4). The number of calls roughly doubles with each step, which is about O(2^n) time.

Why do we need two base cases in recursive Fibonacci?

Each call depends on the two previous values, so the recursion has to stop at both fib(0) and fib(1). With only one base case, calls like fib(n - 2) would skip past it and keep going into negative numbers.

More programs

← All programs

Try AI Flowchart free →