遞歸是一種算法技巧，它允許在函數(shù)內(nèi)部調(diào)用自己。遞歸算法通常用于解決分治問題，即將大問題分解為若干個(gè)小問題，然后遞歸地解決這些小問題。最后將所有小問題的答案合并得到大問題的答案。遞歸算法需要確定一個(gè)終止條件，以防止函數(shù)無限遞歸。

 

遞歸算法幾個(gè)例子：

1. 斐波那契數(shù)列：遞歸算法可以用來求斐波那契數(shù)列的第n項(xiàng)。這個(gè)算法的終止條件是n=1或n=2，其余情況則遞歸求解。
2. 求階乘：遞歸算法可以用來求n的階乘。這個(gè)算法的終止條件是n=1，其余情況則遞歸求解。
3. 求解漢諾塔問題：遞歸算法可以用來解決漢諾塔問題。這個(gè)算法的終止條件是只剩一個(gè)盤子，其余情況則遞歸求解。
4. 二分查找：遞歸算法可以用來實(shí)現(xiàn)二分查找算法。這個(gè)算法的終止條件是找到目標(biāo)元素或查找區(qū)間為空，其余情況則遞歸求解。
5. 遍歷二叉樹: 遞歸算法可以用來遍歷二叉樹。終止條件是遍歷到葉子節(jié)點(diǎn)。

 

　　1、斐波那契數(shù)列：

　　def fibonacci(n):

? 　　? if n == 1 or n == 2:

? ? ?　　? ?return 1

? 　　? else:

? ? ?　　? ?return fibonacci(n-1) + fibonacci(n-2)

　　2、求階乘：

　　def factorial(n):

?　　? ?if n == 1:

? ? ? 　　? return 1

? 　　? else:

? ? ? 　　? return n * factorial(n-1)

 

 

　　3、求解漢諾塔問題：

　　def hanoi(n, src, dst, tmp):

?　　? ?if n == 1:

? ? ? ?　　 print(f"move disk {n} from {src} to {dst}")

?　　? ?else:

? ? ? 　　? hanoi(n-1, src, tmp, dst)

? ? 　　? ? print(f"move disk {n} from {src} to {dst}")

? ? 　　? ? hanoi(n-1, tmp, dst, src)

 

　　4、二分查找：

　　def binary_search(arr, target, low, high):

? 　　? if low > high:

? ? ? 　　? return -1

?　　? ?else:

? ? ?　　? ?mid = (low + high) // 2

? ? ? 　　? if arr[mid] == target:

? ? ? ? ? 　　? return mid

? ? ? ?　　 elif arr[mid] < target:

? ? ? ? ? 　　? return binary_search(arr, target, mid+1, high)

? ? ?　　? ?else:

? ? ? ? ?　　? ?return binary_search(arr, target, low, mid-1)

 

　　5、遍歷二叉樹：

　　class Node:

? ?　　 def __init__(self, val):

? ? ? ?　　 self.val = val

? ? ? 　　? self.left = None

? ? ? ?　　 self.right = None

 

　　def preorder_traversal(root):

? 　　? if root is None:

? ? ? 　　? return

? 　　? print(root.val)

? ?　　 preorder_traversal(root.left)

? 　　? preorder_traversal(root.right)