1package fib
2
3// FibRecursive computes the nth Fibonacci number recursively (O(2^n)).
4func FibRecursive(n int) int {
5	if n <= 1 {
6		return n
7	}
8	return FibRecursive(n-1) + FibRecursive(n-2)
9}
10
11// FibIterative computes the nth Fibonacci number iteratively (O(n)).
12func FibIterative(n int) int {
13	if n <= 1 {
14		return n
15	}
16	a, b := 0, 1
17	for i := 2; i <= n; i++ {
18		a, b = b, a+b
19	}
20	return b
21}