4.1 Introduction
F(n) =
1 if n = 0 or 1
F(n-1) + F(n-2) if n > 1
n 0 1 2 3 4 5 6 7 8 9 10
F(n) 1 1 2 3 5 8 13 21 34 55 89
Pseudo code for the recursive algorithm:
F(n)
1 if n=0 or n=1 then return 1
2 else return F(n-1) + F(n-2)
•
Fibonacci number F(n)
第 1 页 / 共 158 页