美文网首页
栈与递归的实现

栈与递归的实现

作者: 小白要打怪 | 来源:发表于2020-05-06 22:20 被阅读0次

直接调用自己或通过一系列的调用语句间接的调用自己的函数,称为递归函数。
一、许多数学函数就是通过递归定义的,如:
阶乘函数

  •                 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

总结:
一个递归函数的运行过程类似与多个函数的嵌套调用,只是调用函数与被调用函数是同一个函数,因此,和每次调用相关的一个重要概念是递归函数运行的“层次”。
为了保证递归函数正确执行,系统需设立一个“递归工作栈”作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”,其中包括所有的实在参数,所有的局部变量以及上一层的返回地址。每进入一层递归就产生一个新的工作记录压进栈顶。每退出一层递归就从栈顶弹出一个工作记录,则当前执行层的工作记录必是递归工作栈栈顶的工作记录,这个记录为”活动记录“,指示活动记录的栈顶指针称为”当前环境指针“。

相关文章

  • 倒序打印链表

    递归实现 借助栈实现

  • 栈与递归的实现

    栈与递归 栈还有一个重要应用是在程序设计语言中实现递归。一个直接调用自己或通过一系列的调用语句间接的调用自己的函数...

  • 栈与递归的实现

    直接调用自己或通过一系列的调用语句间接的调用自己的函数,称为递归函数。一、许多数学函数就是通过递归定义的,如:阶乘...

  • 尾递归

    尾递归 Lua尾递归的实现 爆栈问题 基于栈实现函数调用的语言都有栈空间的上限,这里拿几个语言举例 运行到2589...

  • 二叉树遍历(递归&非递归实现)

    递归实现: 非递归实现: 基于栈的递归消除: 递归(recursion)就是子程序(或函数)直接调用自己或通过一系...

  • 采用栈结构,递归实现链表的反转

    采用栈结构,递归实现链表的反转 CSDN

  • 面试题6:从尾到头打印链表

    方法一:借助栈 方法二:递归的思想既然想到了用栈来实现这个函数,而递归本质上就是一个栈结构,很自然的想到用递归来实...

  • Depth First Search

    概述 DFS(Depth First Search) => 深度优先搜索算法 => 递归与回溯,通常隐含了栈的实现...

  • 二叉树的遍历

    前中后序的递归实现 前中后序的非递归标准实现 总结 整体的思路是这样的: 指针p指向root,创建栈 当栈不为空或...

  • 【数据结构】【C#】026-二叉树(BT):🌱遍历介绍

    一、递归遍历: 1、先序遍历:2、中序遍历:3、后续遍历:总结规律: 二、非递归遍历:利用栈来实现 非递归算法实现...

网友评论

      本文标题:栈与递归的实现

      本文链接:https://www.haomeiwen.com/subject/ixwgghtx.html