用c表示的递归函数: a(n)=a(n-1)+a(n-2)

Question

我试图为公式编写一个递归函数：

a(n)=a(n-1)+a(n-2)

我试着把它写出来：

 unsigned int ladder(unsigned int n)
{
    unsigned int ret=0;
    if (n < 1)
        return ret;
    ret = ladder(n - 1) + ladder(n - 2);


}

但是当调用梯子(n-2)时，它会进入堆栈溢出。

(由于某种原因，它将n设为一个非常大的整数)

我觉得我错过了一些非常基本的东西，但我想不出是什么。

Answer 1

当n不小于1时，该函数将不返回任何内容。

同样，当n等于1时，表达式n-2产生可以存储在无符号int类型的对象中的最大值。

该函数可以通过以下方式声明和定义

unsigned long long int ladder( unsigned int n )
{
    return n < 2 ? n : ladder( n - 1 ) + ladder( n - 2 );
}

这是一个演示程序。

#include <stdio.h>

unsigned long long int ladder( unsigned int n )
{
    return n < 2 ? n : ladder( n - 1 ) + ladder( n - 2 );
}

int main( void )
{
    for ( unsigned int i = 0; i < 25; i++ )
    {
        printf( "%llu ", ladder( i ) );
    }
    putchar( '\n' );
}

程序输出是

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368