关于递归的问题
本帖最后由 xiaoyao1 于 2024-9-4 04:21 PM 编辑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算出来的，可加了一个打印进去，打印的过程看不明白。
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))
打印的全程如下：
1 1
2
1
1
2
6
1
1
2
1
1
2
6
24
1
1
2
1
1
2
6
1
1
2
1
1
2
6
24
120
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 发表于 2024-9-4 06:30 PM
= =
对栈还是没理解
先去查一下什么是调用约定,搞明白参数是从左往右压栈还是从右往左压栈
大概看了一下是从左往右压栈
那么就是return第一个参数先进栈开始递归,所以打印到24时结束
然后开始第二个参数的递归进栈
因为你是递归
所以每一次进下一个栈的时候又会同时有return的左右两个参数
不妨去看看二叉树的树形结构?
大概就是你这个栈的模样 Lua领域最权威书籍之一《Lua编程(programming in lua) 》中文版 .pdf没这些内容，或者我还没看到？但内容已经涉及了 本帖最后由 vshrd 于 2024-9-4 09:40 PM 编辑
= = 你这个开栈顺序
我没记错的话好像就是二叉树的LFR遍历差不多
好像是叫这个名字吧= = vshrd 发表于 2024-9-4 09:41 PM
你这个开栈顺序
我没记错的话好像就是二叉树的LFR遍历差不多
好像是叫这个名字吧= =
加的那个打印是有点问题的，打印时应该会再一次启动这个函数，也就是会多运行一次。那么对整体进行一个修改：
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)
运行结果如下：
5
4
3
2
1
1
2
6
24
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)需要一直递归运行结束返回时才会执行。
至于栈和堆的概念，栈是先进后出，后进先出，汉诺塔能清晰的感受到。而堆是特殊的树结构， 称之二叉树。
在这个问题上的继续延申，递归和尾递归的概念和区别
local fact
fact = function (n)
if n == 0 then
return 1
else
return n*fact(n-1)
end
end以上是递归，不是尾递归。因为n*fact(n-1)在当前层时并不能得到结果，而是需要递结束后返回时才能够计算得到结果。递归是要通过“递”将算法传递下去，再通过“归”将值一层层返回，所以每递一次就要开一个栈，用于保存算法，直到得到返回值经过计算得到结果，再结束这些栈。当递的层数过长，将会导致栈溢出。
以下是改造成尾递归
local fact
fact = function (n，acc)
if n == 0 then
return acc
else
return fact(n-1 , n*acc)
end
end
对比以上，尾递归的特点就是在“递”的时候就已经就算完毕，递下去的是值，因此不用在递的过程中保存算法等信息，也即不用开栈。这样的话不论多少层都可以进行，不存在溢出的问题，同时保持了递归易理解，编写简洁的特点。以上还可以进行优化成一个参数：
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
页:
[1]