C# Program to Find Fibonacci Number Using Recursion

You can write a C# recursive Fibonacci function like int Fibonacci(int n) { if (n <= 1) return n; return Fibonacci(n - 1) + Fibonacci(n - 2); } which calls itself to calculate Fibonacci numbers.

Examples

Input0

Output0

Input5

Output5

Input10

Output55

How to Think About It

To find the Fibonacci number at position n, check if n is 0 or 1 and return it directly. Otherwise, calculate it by adding the Fibonacci numbers at positions n-1 and n-2 using recursive calls.

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 for n.

Code

csharp

using System;
class Program {
    static int Fibonacci(int n) {
        if (n <= 1) return n;
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
    static void Main() {
        int n = 10;
        Console.WriteLine(Fibonacci(n));
    }
}

Output

55

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

Base cases

Fibonacci(1) = 1, Fibonacci(0) = 0

6

Return Fibonacci(2)

1 + 0 = 1

7

Return Fibonacci(3)

Fibonacci(2) + Fibonacci(1) = 1 + 1 = 2

8

Return Fibonacci(4)

Fibonacci(3) + Fibonacci(2) = 2 + 1 = 3

9

Call Fibonacci(3)

Already calculated as 2

10

Return Fibonacci(5)

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

Call	Result
Fibonacci(0)	0
Fibonacci(1)	1
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, stopping recursion.

Step 2: Recursive Calls

For other values, the function calls itself twice to get the two previous Fibonacci numbers.

Step 3: Combining Results

It adds the two results to get the Fibonacci number for n.

Alternative Approaches

Iterative approach

csharp

using System;
class Program {
    static int Fibonacci(int n) {
        if (n <= 1) return n;
        int a = 0, b = 1, c = 0;
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
    static void Main() {
        Console.WriteLine(Fibonacci(10));
    }
}

This method is faster and uses less memory than recursion.

Memoization (caching results)

csharp

using System;
class Program {
    static int[] memo = new int[100];
    static 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];
    }
    static void Main() {
        Console.WriteLine(Fibonacci(10));
    }
}

Stores results to avoid repeated calculations, improving speed.

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

Time Complexity

The recursive function calls itself twice for each number, leading to exponential time because many calls repeat the same calculations.

Space Complexity

The maximum depth of the recursion stack is n, so space used is proportional to n.

Which Approach is Fastest?

Iterative and memoized methods run in linear time O(n) and are much faster than plain recursion.

Approach	Time	Space	Best For
Recursive (plain)	O(2^n)	O(n)	Simple code, small n
Iterative	O(n)	O(1)	Fast and memory efficient
Memoization	O(n)	O(n)	Fast with recursion, caches results