關于遞歸的總結——漢諾塔、素因數的求解（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)