递归函数与尾递归总结_r语言中的尾递归函数

一、普通递归

递归是一个熟悉而陌生的概念，说它熟悉，是因为人们经常提起它，而说它陌生，指的是人们在实际编程中几乎不会主动使用它。什么是递归呢，给定一个问题，如果本质上它能看做一个调用自身的规模较小的一个子问题来求解，那这种解决方案就是递归；

如何使用递归解决问题：在设计一个递归函数解决一个问题时，通常要注意两个要素，递推关系以及终止条件；而且在思考递推关系时，因为函数是递归调用的，所以尤其要注意逻辑顺序；对于数学问题的计算一般比价简单，对于更为广泛的实际问题，需要更好的抽象思考能力；在面向对象中类的设计里，我们知道继承关系中，构造函数和析构函数都是需要递归调用的，例如在构造函数中要先调用父类的构造函数，然后依次调用子类的构造函数，而析构函数则是正好相反的顺序；这里面其实就是递归函数的原理，那么我们先写一个单继承类模型中构造与析构的递归调用代码；

注意一下两者的区别，构造函数调用的递推逻辑是先调用子类的构造函数，再调用父类的构造函数；而析构函数的调用方式恰恰相反，要注意好这个逻辑，当然有一些递归问题是不需要注意这个，是否需要关注递归内的逻辑顺序需要我们自己根据需求来判断；然而在很多时候，我们都是需要关注顺序的，比如上面的构造函数是前向调用，先调用最深层级的，最后调用自身；而析构函数则是先调用自身，再递归调用其它；

    //constructor
    function InvokeCtor(classtype_){
        if(classtype_.super!=Null){
            InvokeCtor(classtype_.super);
        }
        classtype_.ctor();
    }
    //destructor
    function InvokeDctor(classtype_){
        classtype_.dctor();
        if(classtype_.super!=Null){
            InvokeDctor(classtype_.super);
        }
    }

二、尾递归

尾递归是一种逻辑形式，使用这种形式写出的代码逻辑可以被一部分编译器进行优化；因为尾递归调用函数时，不必再维持调用函数的栈（这一特性叫做尾调用消除），而是只需要为新的被调用函数创建一个栈空间即可；由于尾递归不会浪费栈空间，所以无论多复杂的递归调用都不会导致栈溢出，但是其中的关键是要确保它是一个尾递归；

尾递归的优化主要是对空间复杂度的优化，能够优化栈内存空间，而对时间复杂度没有什么影响；

实现的关键思路就是每次递归调用时都会收集上一层的词法环境，然后将其作为参数传递到函数中；

以斐波那契数列为例，以下给出了斐波那契数列的三种实现方式，第三种方式为尾递归；

--普通递归
local fiber1
fiber1=function(n)
    if n==1 or n==2 then
        return 1
    else
        return fiber(n-1)+fiber(n-2)
    end
end
 
--迭代
local fiber2
fiber2=function(n)
    local a=1
    local b=1
    for i=3,n do
        local tmp=b
        b=a+b
        a=tmp
    end
    return b
end
 
--尾递归
local fiber3
fiber3=function(a,b,n)
    if n<3 then
        return b
    else
        return fiber3(b,a+b,n-1)
    end
end
 
for i=1,5 do
    print(fiber3(1,1,i))
end

三、从普通递归到尾递归的转换

正常递归的求解是将f(n)展开，然后再递归求解；

而尾递归可以理解为循环n次进行求解；

比如对于斐波那契数列，使用尾递归就是求第三项、再第四项直到第n项；而正常递归是从第n项先展开；

尾递归会把每次循环的求解传递给递归函数作为参数，直到递归了n次以后；因此，它的递归函数范式中应该有如下几类参数，循环变量x和循环次数常量n，每次循环产生的结果变量r；

如下所示，展示了斐波那契数列的尾递归转换，阶乘的尾递归转换，以及两者结合的复杂版的转换示例；

注意：关于阶乘，有一些尾递归会写成f(r, n) = f(r*n, n - 1)的形式，这是一种巧妙写法，并不具有通用性，也不符合尾递归的循环思想；  

参考

1.知乎-递归函数（二）：编写递归函数的思路和技巧

2.知乎-什么是尾递归