L04-02. 尾调用(尾递归)

互相调用函数执行原理: 这里介绍函数a调用函数b 在栈中的变化: 

　　函数调用会在内存形成一个"调用记录"，保存调用位置和内部变量等信息。
　　如果在函数 A 的内部调用函数 B，那么在 A 的调用记录上方，还会形成一个 B 的调用记录。等到 B 运行结束，
　　将结果返回到 A，B 的调用记录才会消失。

一. 什么尾调用

　　1. 当函数最后一个动作是调用另外一个函数时，我们称尾调用


function f(x){
  return g(x);
}

　　2. 尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用记录，因为调用位置、内部变量等信息都不会再用到了

function f() 
  local m = 1
  local n = 2
  return g(m + n)
end
f()-- 等同于
g(3)

　　3. 如何判断属于尾调用

function foo2 (n)
    return foo2(n)      --是尾调用, 只能写一个返回值并且这个返回值是他自身, 而且是在return中调用的自身 才称为尾递归
end

--尾调用不一定出现在函数尾部，只要是最后一步操作即可：
function testFunc(arg)
　　if arg > 0 then
　　　　return testFuncA(arg) -- 是尾调用
　　end
　　return testFuncB(arg) -- 也是尾调用
end

　　3. 以下情况, 均不属于尾调用

function foo1 (n)
    foo1(n)             --不是尾递归, 因为没有return就不知道后面是否属于结束语句
end

function f (x)
    g(x)                --不是尾调用, 后面还需要执行return语句
    return
end

function f (x)
    return g(x)+1       --不是尾调用, 最后动作是执行加法运算
end

function f (x)
    return x or g(x)    --不是尾调用, g()即使是多个返回值也会在表达式中必须调整为一个返回值, (最后一步东西需要调整为一个可选值)
end

function f (x)
    return (g(x))       --不是尾调用, g()即使是多个返回值也会在表达式中必须调整为一个返回值, 因为有括号(最后一步东西需要调整为一个可选值)

end

二、尾递归

　　1. 函数调用自身，称为递归。如果尾调用自身，就称为尾递归

　　2. 对于尾递归来说，由于只存在一个调用记录，所以永远不会发生"栈溢出"错误。

 　   3. 将递归改写为尾递归(重要)

--阶乘算法1:
local function Factorial001(num)
    if num == 1 then
        return 1
    end
    return num * Factorial001(num - 1)
end
Factorial001(10)

--阶乘算法2:(尾递归方式)
--在编写递归时, 尽量把所有用到的内部变量改写成函数的参数, 形成尾递归方式
local function Factorial002(num, n)
    if num == 1 then
        return num
    end
    return Factorial002(num - 1, n * num)
end
--这种调用方式一眼看过去不懂第二个参数是干嘛的所有需要使用"将多参数的函数转换成单参数的形式"
Factorial002(10, 1)

--将多参数的函数转换成单参数的形式
local function Factorial003(num)
    return Factorial002(num, 1)
end
--这种方式就正常了
Factorial003(10)

　　4. 菲波那契数列

--输出菲波那契数列
local function Fibonacci2(n1, n2, endNum, tb)
    if n1 > endNum then
       return tb
    end
    table.insert(tb,n1)
    return Fibonacci2(n2 , n2 + n1,endNum,tb)
end

local function Fibonacci(endNum)
    return table.unpack(Fibonacci2(0,1,endNum,{}))
end

print( Fibonacci(100) )