降斐波那契数的递归

Question

我很难理解斐波那契数列递减的递归，尝试手动计算它但没有成功。

在评估代码时，我认为它会从以下内容开始： (5, 1, 2)

但是，它的开头是： (1, 8, 13) (2, 5, 8) 等等

我完全迷失在这里。有人可以解释为什么它会这样吗？

#include <stdio.h>
#include <stdlib.h>


void fib_dec_a ( int n, int f1, int f2 ) {
    if ( n > 1 ){
        fib_dec_a ( n - 1, f2, f1 + f2 );
    }
    printf ("%d\n", f1);
}

int main () {
     int n;
     printf ( "Enter the length of descending Fibonacci sequence: " );
     scanf ( "%d", &n);
     printf ( "\nDescending sequence starting with an n-th element %d :\n", n );
     fib_dec_a (n, 1, 1 );
     return 0;
}

对于 n=6： 8个 5个 3个 2个 1个 1

Answer 1

fib_dec_a是阻塞调用；只有在该函数完成它必须执行的任何指令后，执行才会继续。因此，为了到达 n == 1 案例，必须先完成 n == 2 案例。这同样适用于 n == 3 情况； n == 4 案例必须先完成执行。

因此，n 的较低值的所有 printf 语句将首先执行，因为它们的被调用者 (n + 1) 正在等待此 return 在执行之前。如果将 printf 语句移动到 if (n > 1) 分支上方，您会发现顺序相反。

Answer 2

直到n>1这些函数被递归调用； f(6,1,1) -> f(5,1,2) -> f(4,2,3) -> f(3,3,5) -> f(2,5,8) -> f(1,8,13)

for f(1,8,13) => f1 = 8

然后所有函数以相反的方式完成记录命令运行, 8, 5, 3, 2, 1, 1.

降斐波那契数的递归

Recursion for descending Fibonacci numbers

c

recursion

fibonacci