尾递归：通过斐波那契的迭代法和尾递归法了解

叁歲伎倆 2022-06-04 07:42 180阅读 0赞

**1.斐波那契的递归写法：**

int fib(int n)
    {
        if(n<=2)
        return 1;
        else
        {
            return fib(n-1)+fib(n-2);
        }
    }

其流程图（以求第4个斐波那契数为例）如下：  
![这里写图片描述][SouthEast]

> 缺点：  
> ①只是使用于n比较小的时候，否则**效率低**，**因为会做很多次重复操作**  
> ②而且该例递归属于**多分支递归，容易造成栈溢出**

**2.斐波那契的尾递归写法**

int fib(int first,int second,int n)
    {
        if(n<=2)
        {
     return 1;
        }
        if(3 == n)
        {
     return first+second;
        }
     return fib(second,first+second,n-1);
    }

其流程图（以求第7个斐波那契数为例）如下：  
![这里写图片描述][SouthEast 1]

> 优点：  
> ①**计算结果参与到下一次的计算，从而减少很多重复计算量**  
> ②原本朴素的递归产生的栈的层次像二叉树一样，以指数级增长，但是现在栈的层次却像是数组，**变成线性增长**了，简单来说，原本栈是先扩展开，然后边收拢边计算结果，**现在却变成在调用自身的同时通过参数来计算**。

**3.斐波那契的迭代算法**

int fib(int n)
    {
        int a=1;
        int b=1;
        int c=1;
        while(n>2)
        {
            c=a+b;
            a=b;
            b=c;
            n--;
        }
        return c;
    }

> **尾递归可以转换成迭代算法**

**总结：尾递归的本质是：将单次计算的结果缓存起来，传递给下次调用，相当于自动累积。**

[SouthEast]: /images/20220604/9a8638b0999f4ee98ae8452406538480.png
[SouthEast 1]: /images/20220604/598f4f13c96a4f97a95764ab0b52ef79.png