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

在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的位置，在调用结束后，函数开始返回，此时因为不需要返回值，便返回空。下面的图片可以说明递归调用过程。

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

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)