关于递归的总结——汉诺塔、素因数的求解（Python实现）

不念不忘少年蓝@ 2022-06-10 04:14 136阅读 0赞

在Python函数的学习中，再次对函数的递归感到了迷惑，都说递归逻辑清晰，应用简单，但是在应用中却总有些不理解的地方，甚至感到很疑惑，在此进行总结，希望能理解。首先看一下阶乘的递归求法：

def getNum(num):
    	if num > 1:
    		result = num * getNum(num-1)
    	else:
    		result = 1
    	return result
    a = getNum(5)
    print(a)
    #可以总结一下常见递归的套路
    # def fun(i): 
    # 	if 成立条件:
    # 		递归调用
    # 	else:
    # 		***** 
    #   return *****

我们可以看出递归函数具有几点很重要的要素，首先是递归的跳出条件，类似于循环，总要有跳出条件，没有跳出条件，那么便会无限循环，进入死结。其次便是对自身的调用，比如上面的第三行的result = num \* getNum(num-1)，便是对自身的调用，注意参数的传递，以及我们需要求得的结果。最后便是递归结束后的操作，在阶乘里递归结束后的操作便是返回result(有些函数里我们需要返回空)。下面看一下素因数的求法。代码如下：

#-*- coding:utf-8 -*-
    import math
    def suyinshu(n):
    	for i in range(2,int(math.sqrt(n+1))+1): #range里必须是整数
    		if n%i == 0:
    			print(i)
    			suyinshu(n/i)
    			return 
    	if(n > 1):  #如果是素数
    		print(n)
    suyinshu(100)

很早以前便写过求某一个数n的素因数递归求法的c++版，但是现在再看竟是一头雾水，可见功底还是不到家。首先分析下，求素因数的思路：用n对i(2到根号n)取模，为零的便证明是n的因数，将其输出，之后再用n/i作为参数，递归调用函数，再次求n（n/i）的因数，如果没有因数（证明本身是素数），便将n输出。注意return的位置，在调用结束后，函数开始返回，此时因为不需要返回值，便返回空。下面的图片可以说明递归调用过程。

![Center][]

![Center 1][]

另外说到递归便不得不提汉诺塔，所谓的完美的递归，便是汉诺塔，代码如下：

def move(n, a, buffer, c):
        if(n == 1):
            print(a,"->",c)
            return
        move(n-1, a, c, buffer)
        move(1, a, buffer, c)
        move(n-1, buffer, a, c)
    move(3, "a", "b", "c")

理解起来很是抽象，但是原理很简单，有a、b、c三个柱子，a上有n个盘子，我们的目的便是将n个盘子原封不动的放到c上，分为三步：
    move(n-1, a, c, buffer)
    第一步，将a柱上面的n-1个盘子通过c按照从小到大的规则先移动到缓冲区buffer（b）。
    move(1, a, buffer, c)
    第二步，a上的n-1个盘子的递归移动完成之后，把a柱上的最后一个盘子通过b（buffer）移动到c,也就是所谓的最底下的盘子
    move(n-1, buffer, a, c)
    第三步，将b（buffer）上的n-1个盘子通过a移动到c上
    递归跳出条件便是n==1，此时a上只有一个盘子，示意将a移动到c上便可结束。
    这便是递归，看似不可思议，但就是如此执行。

同时我们要理解一点，用递归解决的问题，都可以转化为循环执行，因为递归实质是调用栈，而栈和递归又可以相互转化。因此我们可以将素因数的求法用循环表示(汉诺塔的递归方法不再给出)：

def suyinshu2(n):
    	for i in range(2,int(math.sqrt(n))):
    		while n%i == 0:
    			print(i)
    			n = n/i
    	if(n > 1):
    		print(n)
    suyinshu2(100)

[Center]: /images/20220610/4f8f1ef63e244c87a173277e45e814b1.png
[Center 1]: /images/20220610/5a6dda5a3f6f4b51a7c43919127c02e3.png