• 欢迎光临~

递归

开发技术 开发技术 2022-10-27 次浏览

递归

递归是栈的应用之一
举一个斐波那契数列的例子

int Fbi(unsigned i)
{
    if (i < 2)
        return i;
    return Fbi(i - 1) + Fbi(i - 2);
}

我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称作递归函数

在高级语言中,调用自己和调用其他函数没有区别本质的不同,我们可以把一个递归函数看作是在调用另一个函数,只不过这个函数和自己长得一模一样而已

写递归程序最要防止的就是无限递归了,所以,每个递归定义必须要有至少一个条件,满足时递归不会再进行,即不再应用自身而是返回值并退出
比如斐波那契数列的例子,输入的i是自然数,随着i的逐渐减小,总会使得i < 2,这样就可以return i不用继续递归了

int Fbi(int i)
{
    int a = 0, b = 1;
    while (i-- != 0)
    {
        int t = a + b;
        a = b; b = t;
    }
    return a;
}

观察两种实现代码,迭代和递归的区别是:迭代使用循环结构,递归使用选择结构
使用递归能使程序结构更清晰、简洁,但是大量使用递归会耗费大量内存和时间,因此我们应视情况使用不同的代码实现方式

程序员灯塔
转载请注明原文链接:递归
喜欢 (0)