Python之递归函数 - 汉诺塔的魅力

矫情吗；* 2022-04-11 13:48 141阅读 0赞

--------------------

任务描述

在Python函数内部，我们可以去调用其他函数。所以如果一个函数在内部调用自身，这个函数我们就称为递归函数。本关我们将以汉诺塔的例子来感受递归函数的方法与应用。

汉诺塔问题源于印度一个古老传说。相传大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？

![169967][]

本关目标就是通过对汉诺塔问题的探讨，让读者了解并掌握递归函数的相关知识。

相关知识

在编程语言中，如果一种计算过程的其中每一步都会用到前一步或前几步的结果，这个计算过程就可以称为递归的。而用递归计算过程定义的函数，则被称为递归函数。递归函数应用很广泛，例如连加、连乘及阶乘等问题都可以利用递归思想来解决。而汉诺塔问题也是递归函数的经典应用。

汉诺塔问题的解决思路：如果我们要思考每一步怎么移可能会非常复杂，但是可以将问题简化。我们可以先假设除`a`柱最下面的盘子之外，已经成功地将`a`柱上面的63个盘子移到了`b`柱，这时我们只要再将最下面的盘子由`a`柱移动到`c`柱即可。

![169968][]

当我们将最大的盘子由`a`柱移到`c`柱后，`b`柱上便是余下的`63`个盘子，`a`柱为空。因此现在的目标就变成了将这`63`个盘子由`b`柱移到`c`柱。这个问题和原来的问题完全一样，只是由`a`柱换为了`b`柱，规模由`64`变为了`63`。因此可以采用相同的方法，先将上面的`62`个盘子由`b`柱移到`a`柱，再将最下面的盘子移到`c`柱。

以此内推，再以`b`柱为辅助，将`a`柱上面的`62`个圆盘最上面的`61`个圆盘移动到`b`柱，并将最后一块圆盘移到`c`柱。

我们已经发现规律，我们每次都是以`a`或`b`中一根柱子为辅助，然后先将除了最下面的圆盘之外的其他圆盘移动到辅助柱子上，再将最底下的圆盘移到c柱子上，不断重复此过程。

这个反复移动圆盘的过程就是递归，例如我们每次想解决`n`个圆盘的移动问题，就要先解决`（n-1)`个盘子进行同样操作的问题。

我们先假设`a`柱上只有`3`个圆盘，利用Python进行编程实现圆盘的移动，代码如下：

1.  `def move(n, a, b, c):`
2.  `if(n == 1):`
3.  `print(a,"->",c)`
4.  `return`
5.  `move(n-1, a, c, b)`
6.  `move(1, a, b, c)`
7.  `move(n-1, b, a, c)`
8.   
9.  `move(3, "a", "b", "c")`

函数运行结果：

1.  `a -> c`
2.  `a -> b`
3.  `c -> b`
4.  `a -> c`
5.  `b -> a`
6.  `b -> c`
7.  `a -> c`

程序分析：

首先我们定义了一个函数`move(n,a,b,c)`,参数`n`代表`a`柱上的圆盘个数，`a`,`b`,`c`三个柱子的顺序代表要将`a`柱上的圆盘最终移动到`c`柱上，然后`b`柱作为中间柱。

我们在递归函数中肯定会有终止递归的条件，`2`到`4`行的代码就是表示当`a`柱上的圆盘个数为1的时，就中止递归并返回,因为此时`a`柱上面只有一个圆盘的时候肯定就是直接把圆盘从`a`柱移动到`c`柱了。

第`5`行的代码`move(n-1, a, c, b)`表示先得把`a`柱上的`n-1`个圆盘从`a`柱移动到`b`柱，这时`c`柱是中间辅助柱。

第`6`行的代码`move(1, a, b, c)`就是条件`n=1`的时候，表示把`a`柱上剩下的`1`个最大圆盘从`a`柱移动到`c`柱。

第`7`行的代码`move(n-1, b, a, c)`表示现在`n-1`个圆盘转移到要`b`柱上了，还是递归调用`move`函数，将`n-1`个圆盘从`b`柱移动到`c`柱，这时`a`柱是中间辅助柱。

最后我们调用`move`函数将`3`个圆盘从`a`柱移动到到`c`柱，当移动`64`个圆盘时，只需要将调用函数`move(n,a,b,c)`中的`n`变为64即可，这个计算量是十分巨大的，也只能交给计算机去解决。

小结：

我们通过汉诺塔的例子感受了递归函数的基本思路，并尝试解决了一个具体问题。递归函数的优点是定义清晰，思路简洁，能够极大简化编程过程。理论上，所有的递归函数都可以用循环的方法代替，但循环方法的编程过程要比递归函数复杂很多。

编程要求

本关的编程任务是补全`src/step1/recursive.py`文件的代码，实现相应的功能。具体要求如下：

*  定义一个函数`fact(n)`，实现的功能是对输入的正整数`n`进行`n!`运算。
 *  调用函数`fact(n)`，对输入的正整数`n`进行阶乘运算，并输出计算结果。

本关涉及的代码文件`src/step1/recursive.py`的代码框架如下：

1.  `#coding=utf-8`
2.   
3.  `#输入正整数n`
4.  `n = int(input())`
5.   
6.  `# 请在此添加代码，实现n!`
7.  `#********** Begin *********#`
8.   
9.   
10.  
11.  
12. `#********** End **********#`

测试说明

本关的测试文件是`src/step1/recursive.py`，测试过程如下：

1.  平台自动编译生成`recursive.exe`;
2.  平台运行`recursive.exe`，并以标准输入方式提供测试输入；
3.  平台获取`recursive.exe`输出，并将其输出与预期输出对比。如果一致则测试通过，否则测试失败。

以下是平台对`src/step1/recursive.py`的样例测试集：

测试输入：  
`5`  
预期输出：  
`120`

测试输入：  
`6`  
预期输出：  
`720`

测试输入：  
`7`  
预期输出：  
`5040`

测试输入：  
`8`  
预期输出：  
`40320`

#coding=utf-8
    
    #输入正整数n
    n = int(input())
    
    # 请在此添加代码，实现n!
    #********** Begin *********#
    
    def fact(n):
        sum = 0
        if(n<1):
            sum = 1
        else:
            sum = n*fact(n-1)
        return (sum)
    
    
    
    
    #********** End **********#
    print(fact(n))

[169967]: https://educoder.trustie.net/attachments/download/169967
[169968]: https://educoder.trustie.net/attachments/download/169968

发表评论取消回复

表情：

评论列表（有 0 条评论，141人围观）

还没有评论，来说两句吧...

相关阅读

相关【Python 递归】汉诺塔问题

问题描述：汉诺塔问题是一类经典的编程问题，主要使用了递归的思想。递归：最重要的有两个方面：第一个是基例（即终止条件），第二个是递归链条（即n和n-1的关系），只要找准了这

淡淡的烟草味﹌/ 2023年10月19日 08:06/ 0 赞/ 137 阅读

相关 python 递归-汉诺塔

汉诺塔 a = "A" b = "B" c = "C" def hano(a, b, c, n): if n == 1

清疚/ 2023年08月17日 16:19/ 0 赞/ 135 阅读

相关递归（4）—— 汉诺塔

分析：初始的N个从小到大的盘子，N是最大编号。 1-N从A移动到B，C作为辅助。等价于： 1、1-N-1从A移动到C，B作为

短命女/ 2022年12月02日 03:52/ 0 赞/ 174 阅读

相关递归应用之汉诺塔

问题描述：　　有一个梵塔，塔内有三个座A、B、C，A座上有诺干个盘子，盘子大小不等，大的在下，小的在上（如图）。把这些个盘子从A座移到C座，中间可以借用B座但每次只能允

╰+攻爆jí腚メ/ 2022年07月13日 12:11/ 0 赞/ 182 阅读

相关 Python笔记-递归函数、汉诺塔

递归函数 1、如果一个函数在内部调用自身本身，这个函数就是递归函数。 2、使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，

淡淡的烟草味﹌/ 2022年06月18日 09:17/ 0 赞/ 132 阅读

相关 Python递归之汉诺塔

汉诺塔永远都是递归中的经典汉诺塔一般有两种返回结果，一种是计算移动的次数，另一种是打印输入移动的步骤。假设有A，B，C三个柱子，初始时盘子都在A柱子上，需要借助B做中转

桃扇骨/ 2022年06月08日 04:45/ 0 赞/ 216 阅读

相关汉诺塔递归问题

汉诺塔递归是一个用到了递归思想的经典问题，看过相关借时候其实我仍然还是没有完全理解，但是先把代码扔在博客上，慢慢消化这个问题 include <stdio.h>

迈不过友情╰/ 2022年05月26日 02:37/ 0 赞/ 228 阅读

相关 Python之递归函数 - 汉诺塔的魅力

-------------------- 任务描述在Python函数内部，我们可以去调用其他函数。所以如果一个函数在内部调用自身，这个函数我们就称为递归函数。本关我们将以

矫情吗；*/ 2022年04月11日 13:48/ 0 赞/ 142 阅读

相关递归（汉诺塔）

> 算法思路：略 > > > > \ include <stdio.h> > void hanoi ( int n, char a, char b, char

àì夳堔傛蜴生んèń/ 2022年03月24日 21:10/ 0 赞/ 248 阅读

相关汉诺塔递归思维

汉诺塔比较经典的实现是利用递归，但也可以利用堆栈。题意理解：有A,B,C三个柱子，将A柱子上的N个盘子（从大到小排列）移到C柱子上，每次只允许移动一个盘子，并且保证每个柱子

短命女/ 2021年12月03日 06:37/ 0 赞/ 315 阅读