关于递归的问题

xiaoyao1

[Lua] 纯文本查看 复制代码

local fact
fact = function (n)
    if n == 0 then
        return 1
    else
        return n*fact(n-1)
    end
end
print(fact(5))

结果是能预计的120，应该是5*4*3*2*1算出来的，可加了一个打印进去，打印的过程看不明白。

[Lua] 纯文本查看 复制代码

local fact
fact = function (n)
    if n == 0 then
        return 1
    else
        return n*fact(n-1) ，print(n*fact(n-1))
    end
end
print(fact(5))

打印的全程如下：
[15:57:53] 1[15:57:53] 1
[15:57:53] 2
[15:57:53] 1
[15:57:53] 1
[15:57:53] 2
[15:57:53] 6
[15:57:53] 1
[15:57:53] 1
[15:57:53] 2
[15:57:53] 1
[15:57:53] 1
[15:57:53] 2
[15:57:53] 6
[15:57:53] 24
[15:57:53] 1
[15:57:53] 1
[15:57:53] 2
[15:57:53] 1
[15:57:53] 1
[15:57:53] 2
[15:57:53] 6
[15:57:53] 1
[15:57:53] 1
[15:57:53] 2
[15:57:53] 1
[15:57:53] 1
[15:57:53] 2
[15:57:53] 6
[15:57:53] 24
[15:57:53] 120
[15:57:53] 120
按照对递归的理解，想象中打印出来的形式是：5,20,60,120,120（计算的过程：5,5*4,5*4*3，5*4*3*2，5*4*3*2*1，5*4*3*2*1*1）。
现在按照真实的打印全程，这递归搞不对啊。

vshrd

= =
对栈还是没理解
先去查一下什么是调用约定,搞明白参数是从左往右压栈还是从右往左压栈
然后根据开栈顺序自己画个图简单理一下就行了
打印出来的东西没啥问题= =

vshrd

vshrd 发表于 2024-9-4 06:30 PM
= =
对栈还是没理解
先去查一下什么是调用约定,搞明白参数是从左往右压栈还是从右往左压栈

大概看了一下是从左往右压栈
那么就是return第一个参数先进栈开始递归,所以打印到24时结束
然后开始第二个参数的递归进栈

因为你是递归
所以每一次进下一个栈的时候又会同时有return的左右两个参数
不妨去看看二叉树的树形结构?
大概就是你这个栈的模样

xiaoyao1

Lua领域最权威书籍之一《Lua编程(programming in lua) 》中文版 .pdf没这些内容，或者我还没看到？但内容已经涉及了

vshrd

= =

vshrd

你这个开栈顺序
我没记错的话好像就是二叉树的LFR遍历差不多
好像是叫这个名字吧= =

xiaoyao1

vshrd 发表于 2024-9-4 09:41 PM
你这个开栈顺序
我没记错的话好像就是二叉树的LFR遍历差不多
好像是叫这个名字吧= =

加的那个打印是有点问题的，打印时应该会再一次启动这个函数，也就是会多运行一次。那么对整体进行一个修改：

[Lua] 纯文本查看 复制代码

local fact
fact = function (n)
    if n == 0 then
        return 1
    else
    
        print(n)
        m=n*fact(n-1)
        print(m)
        
        return m
    end
end
fact(5)

运行结果如下：
[15:48:21] 5
[15:48:21] 4
[15:48:21] 3
[15:48:21] 2
[15:48:21] 1
[15:48:21] 1
[15:48:21] 2
[15:48:21] 6
[15:48:21] 24
[15:48:21] 120

这个结果就可以非常直观的观察到递归的过程。在实际运行中，fact(5)运行函数，当运行到第8行时，接下来是没有就执行第9行的，而是在这里执行fact(n-1)，也就是fact(4)，同样到第8行，也去执行fact(3)，就这样直到运行到fact(0)，给了返回值1，接着就进行到fact(1)(也就是1），运行fact(1)中的第9行及return，返回了fact(2)（也就是2）……就这样直到返回到fact(5)=120，递归结束。
放一个图说明

再看打印结果，n是先打印完毕，再打印了m。因为第7行print(n)，每运行一次函数，就会打印一次n，而print(m)需要一直递归运行结束返回时才会执行。
至于栈和堆的概念，栈是先进后出，后进先出，汉诺塔能清晰的感受到。而堆是特殊的树结构， 称之二叉树。

xiaoyao1

在这个问题上的继续延申，递归和尾递归的概念和区别

[Lua] 纯文本查看 复制代码

local fact
fact = function (n)
    if n == 0 then
        return 1
    else
        return n*fact(n-1)
    end
end

以上是递归，不是尾递归。因为n*fact(n-1)在当前层时并不能得到结果，而是需要递结束后返回时才能够计算得到结果。递归是要通过“递”将算法传递下去，再通过“归”将值一层层返回，所以每递一次就要开一个栈，用于保存算法，直到得到返回值经过计算得到结果，再结束这些栈。当递的层数过长，将会导致栈溢出。
以下是改造成尾递归

[Lua] 纯文本查看 复制代码

local fact
fact = function (n，acc)
    if n == 0 then
        return acc
    else
        return fact(n-1 , n*acc)
    end
end

对比以上，尾递归的特点就是在“递”的时候就已经就算完毕，递下去的是值，因此不用在递的过程中保存算法等信息，也即不用开栈。这样的话不论多少层都可以进行，不存在溢出的问题，同时保持了递归易理解，编写简洁的特点。以上还可以进行优化成一个参数：

[Lua] 纯文本查看 复制代码

function fact(n)
    local function fact_helper(n, acc)
        if n == 0 then
            return acc
        else
            return fact_helper(n - 1, n * acc)
        end
    end
    return fact_helper(n, 1)
end