直接调用自己或通过一系列的调用语句间接的调用自己的函数，称为递归函数。
一、许多数学函数就是通过递归定义的，如：
阶乘函数
1 若n=0 f(n) = n*f(n-1) 若n>0
2阶Fibonacci函数
0 若n=0 Fib(n) = 1 若n=1 Fib(n-1)+Fib(n-2) 其他情况
Ackerman函数
n+1 m = 0 Ack(m,n)= Ack(m-1,1) n = 0 Ack(m-1,Ack(m,n-10） 其他情况
二、有些数据结构，如二叉树，广义表等，由于结构本身固有的递归特性，则它们的操作可递归的描述
三、有一类问题，虽然问题本身没有明显的递归结构，但用递归求解比迭代求解更简单，如八皇后问题，汉诺塔问题
n阶Hanoi塔问题：
假设有3个分别命名为X、Y、Z的塔座，在塔座X上插有n个直径大小各不同、依小到大编号为1，2，...，n的圆盘。现要求将X轴上的n个圆盘移至塔座Z上并仍按同样顺序叠排，圆盘移动时必须遵循下列规则：
1.每次只能移动一个圆盘
2.圆盘可以插在X 、Y、Z中的任一塔座上
3.任何时刻都不能将一个较大的圆盘压在较小的圆盘上。
如何实现移动圆盘的操作呢?
当n=1时，问题比较简单，只要将编号为1的圆盘从塔座X直接移至塔座Z上即可；
当n>1时，需利用塔座Y作为辅助塔，若能设法将压在编号为n的圆盘之上的n-1个圆盘从塔座X移至塔座Y上，则可先将编号为n的圆盘从塔座X移至塔座Z上，然后再将塔座Y上的n-1个圆盘移至塔座Z上。
而如何将n-1个圆盘从一个塔座移至另一个塔座的问题是一个和原问题具有相同特征属性的问题，只是问题的规模小1，因此可以用同样的方法求解。
代码：
local count = 0 -- 移动次数
function move (x, n,z)
count = count + 1
print(string.format("%d Move Disk %d from %s to %s", count, n, x, z))
end
function hanoi(n, x, y, z)
if n == 1 then
move(x,1,z) -- 编号为1的盘从x移到z
else
hanoi(n-1, x,z,y) -- x塔上编号为1至n-1的盘从x移到y，以z为辅助塔
move(x,n,z) -- 编号为n的盘从x移到z
hanoi(n-1, y,x,z) -- y塔上标号为1至n-1的盘从y移到z，以x为辅助塔
end
end
hanoi(3,"A","B","C")
输出
1 Move Disk 1 from A to C
2 Move Disk 2 from A to B
3 Move Disk 1 from C to B
4 Move Disk 3 from A to C
5 Move Disk 1 from B to A
6 Move Disk 2 from B to C
7 Move Disk 1 from A to C
总结：
一个递归函数的运行过程类似与多个函数的嵌套调用，只是调用函数与被调用函数是同一个函数，因此，和每次调用相关的一个重要概念是递归函数运行的“层次”。
为了保证递归函数正确执行，系统需设立一个“递归工作栈”作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括所有的实在参数，所有的局部变量以及上一层的返回地址。每进入一层递归就产生一个新的工作记录压进栈顶。每退出一层递归就从栈顶弹出一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，这个记录为”活动记录“，指示活动记录的栈顶指针称为”当前环境指针“。
网友评论