F#递归地理解Fibbonacci序列

Question

这可能听起来像学校的作业,但事实并非如此!

我做了一个递归函数从Fibonacci序列返回一个值.

let rec FoneFive n =
    match n with
    | 1 | 2 -> 1
    | n -> FoneFive(n-1) + FoneFive(n-2)

printfn "%A" (FoneFive 6)

这个递归函数发生了什么？FoneFive 6尽可能给出8.但为什么？

我看待它的方式:从n = 6开始,得出结论6不是1或2.所以它调用FoneFive(n-1) + FoneFive(n-2).(这可能是我错误的地方.但我看到的方式是,除非n为1或2,否则不会返回任何内容.所以从我的观点来看,它会缩小n = 1或2,然后说1 + 1当然是2.)

有人能告诉我它是如何返回8的吗？

Answer 1

计算FoneFive(6)需要计算FoneFive(5)和FoneFive(4)
(as 5和4are n-1和n-2for n=6)

计算FoneFive(5)需要计算FoneFive(4)和FoneFive(3)
(as 4和3are n-1和n-2for n=5)

计算FoneFive(4)需要计算FoneFive(3)和FoneFive(2)
(as 3和2are n-1和n-2for n=4)

计算FoneFive(3)需要计算FoneFive(2)和FoneFive(1)
(as 2和1are n-1和n-2for n=3)

无论FoneFive(1)和FoneFive(2)回报1
等等FoneFive(3) = FoneFive(2) + FoneFive(1) = 1 + 1 = 2
等等FoneFive(4) = FoneFive(3) + FoneFive(2) = 2 + 1 = 3
等等FoneFive(5) = FoneFive(4) + FoneFive(3) = 3 + 2 = 5
等等FoneFive(6) = FoneFive(5) + FoneFive(4) = 5 + 3 = 8