Skip to content
Shadow Cipher

Fibonacci Sequence

// Function to calculate the nth Fibonacci number
int fibonacci(int n) {
    // Base case: If n is 0 or 1, return n
    // This is because the Fibonacci series starts with 0 and 1
    if(n <= 1)
        return n;


    // Recursive case: Fibonacci of n is sum of Fibonacci of (n-1) and (n-2)
    // The function calls itself to calculate the previous two Fibonacci numbers
    return fibonacci(n - 1) + fibonacci(n - 2);
}
Example Walkthrough:
  • fibonacci(5) calls fibonacci(4) and fibonacci(3):
    • fibonacci(5) = fibonacci(4) + fibonacci(3)
  • fibonacci(4) calls fibonacci(3) and fibonacci(2):
    • fibonacci(4) = fibonacci(3) + fibonacci(2)
  • fibonacci(3) calls fibonacci(2) and fibonacci(1):
    • fibonacci(3) = fibonacci(2) + fibonacci(1)
  • fibonacci(2) calls fibonacci(1) and fibonacci(0):
    • fibonacci(2) = fibonacci(1) + fibonacci(0)
    • Since fibonacci(1) is 1 and fibonacci(0) is 0, return 1 + 0 = 1.
  • Now, substitute the results step by step:
    • fibonacci(3) = 1 + 1 = 2
    • fibonacci(4) = 2 + 1 = 3
    • fibonacci(5) = 3 + 2 = 5
Final Result:

For n = 5, the Fibonacci number is 5.