遞歸的概念

程序調用自身的編程技巧稱為遞歸（ recursion）。遞歸做為一種算法在程序設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。

我會寫先介紹遞歸的基本思想，然后再以后的文章中介紹一下遞歸的衍生算法，比如：回溯算法、分治法、DFS等。

設計遞歸的思路

通常我們一提到遞歸就立馬想到了遞歸的兩個重要部分：終止條件與循環(huán)部分。遞歸的設計思路是很像我門做數學題：根據已知條件找規(guī)律，利用遞推式求解未知變量。但是我們作為開發(fā)者面對的是計算機，我們需要用程序語言設計出遞歸的算法去解決問題。下面是遞歸設計的四個重要要素：

接收的參數

返回值

終止條件

遞歸拆解：如何遞歸下一層

遞歸實例

俗話說的好：”孰能生巧“，光說不練，假把式。光用文字去解釋遞歸如何如何讓地去設計，倒不如多花時間從易到難循序漸進做大量練習，通過大量的練習，去尋找其中的規(guī)律。

實例1：n的階乘

# 遞歸實現N的階乘 def fact_resursion(n):# 終止條件if n==1:return 1else:return n*fact_resursion(n-1) # 循環(huán)部分print(fact_resursion(5))

運行結果：120

實例2：斐波那契數列

這里簡單的解釋一下斐波那契數列：F(0) = 0 , F(1) = 1
F(N) = F(N-1) + F(N-2) , N>1 數列前幾項如下：
0 1 1 2 3 5 8 13 …

# 遞歸實現斐波那契數列F(N)的計算 def fun(n):# 終止條件if n <=1:return nelse:return fun(n-1) + fun(n-2) # 循環(huán)部分 print(fun(8))

運行結果：21

實例3：小青蛙跳臺階

一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。

解析：
每次跳的時候，小青蛙可以跳一個臺階，也可以跳兩個臺階，也就是說，每次跳的時候，小青蛙有兩種跳法。
第一種跳法：第一次我跳了一個臺階，那么還剩下n-1個臺階還沒跳，剩下的n-1個臺階的跳法有f(n-1)種。

第二種跳法：第一次跳了兩個臺階，那么還剩下n-2個臺階還沒，剩下的n-2個臺階的跳法有f(n-2)種。

所以，小青蛙的全部跳法就是這兩種跳法之和了，即 f(n) = f(n-1) + f(n-2)。至此，等價關系式就求出來了。

def func(n):if n<=2:return nreturn func(n-1) + func(n-2) print(func(4))

運行結果：5

實例3：列表反轉

# 遞歸實現列表反轉 def rev(alist,left,right):if left >= right: # 終止條件returnrev(alist,left+1,right-1)# 循環(huán)部分alist[left],alist[right] = alist[right],alist[left] alist = [1,2,3,4,5,6] left = 0 right = len(alist) - 1 rev(alist,left,right) print(alist)

運行結果：[6, 5, 4, 3, 2, 1]

實例4：字符串反轉

注意：有人可能會覺得字符串反轉和列表反轉難道不是一樣的嗎？
如果用反轉列表的方法去反轉字符串會出現一下錯誤：

TypeError: ‘str’ object does not support item assignment

在python中，字符串是不可變對象，不能通過下標的方式直接賦值修改。同樣的不可變對象還有：數字、字符串和元組。

直觀一點舉個小例子：
s = “abcd”
x = s[2]
print(x) => ‘c’

但是直接賦值：s[2] = ‘h’ 卻會報錯

# 遞歸實現字符串的反轉 def rvs(s):# 終止條件if len(s) == 1:return selse:return rvs(s[1:])+s[0] # 循環(huán)部分 print(rvs("abcdefg"))

運行結果：gfedcba

實例5：鏈表反轉

注意：因為實現鏈表反轉需要自己創(chuàng)建一個鏈表類和方法，比較麻煩我們就直接用leetcode的206題：鏈表反轉。

代碼：

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution:def reverseList(self, head: ListNode) -> ListNode:# 方法一：雙指針# pre,cur = None,head# while cur:# next = cur.next# cur.next = pre# pre = cur# cur = next# return pre# 方法二： 遞歸# 邊界條件 和 終止條件if head == None or head.next == None:return head# 循環(huán)部分 newhead = self.reverseList(head.next)head.next.next = headhead.next = Nonereturn newhead

實例6：漢諾塔游戲

漢諾塔問題是一個經典的問題。漢諾塔（Hanoi Tower），又稱河內塔，源于印度一個古老傳說。大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，任何時候，在小圓盤上都不能放大圓盤，且在三根柱子之間一次只能移動一個圓盤。問應該如何操作？

假設三根柱子分別為：A，B，C。A柱子上有n個盤子，B，C為空。請問每一步該如何移動？

# 漢諾塔 count = 1 n = 4 def move(n,a,b,c):global countif n == 1:print(count,":",a, '-->', c)count += 1else:move(n-1, a, c, b)print(count,":",a, '-->', c)count += 1move(n-1, b, a, c) print(f'把A柱子的{n}個盤子全部移到C柱子的順序為：') move(n, 'A', 'B', 'C')

運行結果：
把把A柱子的4個盤子全部移到C柱子的順序為：
1 : A --> B
2 : A --> C
3 : B --> C
4 : A --> B
5 : C --> A
6 : C --> B
7 : A --> B
8 : A --> C
9 : B --> C
10 : B --> A
11 : C --> A
12 : B --> C
13 : A --> B
14 : A --> C
15 : B --> C

例子7：科赫雪花

利用python的turtle庫繪制科赫雪花，如下圖所示：

# 科赫雪花 # -*- coding: utf-8 -*- import turtle def koch(size,n):"""函數koch用遞歸思想繪制一段N階曲線"""if n == 0:turtle.fd(size) #遞歸基例(終止條件)，0階曲線即為一條直線else:for i in [0,60,-120,60]: #通過改變方向，繪制四條線段turtle.left(i)koch(size/3,n-1) # 循環(huán)部分 def main():"""定義main函數調用koch""" turtle.setup(600,600)turtle.penup()turtle.goto(-250,100)turtle.pendown()turtle.pensize(2)n = 3for i in range(0,3):koch(500,n)turtle.right(120)turtle.hideturtle()turtle.done() main()

運行結果：

總結

以上是生活随笔為你收集整理的递归算法（一）递归概念与思路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。