尾递归优化

what

一个函数里的最后一个动作是返回一个函数的调用结果的情形，即最后一步新调用的返回值直接被当前函数的返回结果。

此时，该尾部调用位置被称为尾位置。尾调用中有一种重要而特殊的情形叫做尾递归。经过适当处理，尾递归形式的函数的运行效率可以被极大地优化。尾调用原则上都可以通过简化函数调用栈的结构而获得性能优化（称为“尾调用消除”），但是优化尾调用是否方便可行取决于运行环境对此类优化的支持程度如何。

eg

function story() {
    从前有座山，山上有座庙，庙里有个老和尚，一天老和尚对小和尚讲故事：story() // 尾递归，进入下一个函数不再需要上一个函数的环境了，得出结果以后直接返回。
}

function story() {
    从前有座山，山上有座庙，庙里有个老和尚，一天老和尚对小和尚讲故事：story()，小和尚听了，找了块豆腐撞死了 // 非尾递归，下一个函数结束以后此函数还有后续，所以必须保存本身的环境以供处理返回值。
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdint>

using namespace std;


class fib {
    typedef uint64_t ll;
public:
    static ll fib_normal(ll n) {
        if (n <= 1) {
            return 1;
        }
        return  fib_normal(n - 1) + fib_normal(n - 2);
    }
    static ll fib_tru(ll n, ll ac1 = 1, ll ac2 = 1) {
        if (n <= 1) {
            return ac2;
        }
        return fib_tru(n - 1, ac2, ac1 + ac2);
    }
};


int main() {
    cout << fib::fib_tru(10000000000) << endl;
    return 0;
}

ref

• https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.