# Divide-and-conquer algorithm: Fibonacci number

# Fibonacci number

n   => 0  1  2  3  4  5  6   7   8   9  10  11   12
F_n => 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

1
2

# General formula

# Divide-and-conquer

# Iterative case

# General formula

# Example

# Base case

# Coding

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

print(fibonacci(12))

1
2
3
4
5
6
7
8
9

OUTPUT