F# 递归理解斐波那契数列

Question

这听起来像是学校作业，但事实并非如此！

我创建了一个递归函数 return 从斐波那契数列中提取一个值。

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)。（这可能是我弄错的地方。但我的看法是 return 什么都没有，除非 n 是 1 或 2。所以从我的角度来看，它会缩小 n = 1 或 2 并且通过说 1 + 1 当然是 2.)

谁能告诉我 returns 8 是怎么来的？

Answer 1

计算FoneFive(6)需要计算FoneFive(5)和FoneFive(4)
（因为 5 和 4 对于 n=6 是 n-1 和 n-2）

计算FoneFive(5)需要计算FoneFive(4)和FoneFive(3)
（因为 4 和 3 对于 n=5 是 n-1 和 n-2）

计算FoneFive(4)需要计算FoneFive(3)和FoneFive(2)
（因为 3 和 2 对于 n=4 是 n-1 和 n-2）

计算FoneFive(3)需要计算FoneFive(2)和FoneFive(1)
（因为 2 和 1 对于 n=3 是 n-1 和 n-2）

FoneFive(1) 和 FoneFive(2) returns 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

Answer 2

好的，我现在明白了。可以这么说，每当 n 不是 1 或 2 时，它就会将自己分成两部分，然后如果 n 也不是 1 或 2，则再次将自己分成两部分。

f6 = f5 + f4
f5 + f4 = f4 + f3 + f3 + (f2=1)
f4 + f3 + f3 + (f2=1) = f3 + (f2=1) + (f2=1) + (f1=1) + (f2=1) + (f1=1) + 1
f3 + 1 + 1 + 1 + 1 + 1 + 1 = (f2=1) + (f1=1) + 1 + 1 + 1 + 1 + 1 + 1
(f2=1) + (f1=1) + 1 + 1 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8

F# 递归理解斐波那契数列

F# Understanding the Fibbonacci Sequence Recursively

math

recursion

f#

fibonacci