講述遞歸，即調用函數自身的編程方法，遞歸需要的 基線條件即最簡單狀態，遞歸條件即指導函數將條件引向最簡狀態。由于遞歸的特殊性，調用棧必不可少，棧為先進后出的數據結構，類似高斯消元法的“向前——向后”，我們將問題逐漸堆高簡化，再從高處解決，帶入底端，此為調用棧。

1 遞歸

假設要找一把鑰匙,而鑰匙在下面的盒子里.

使用一種方法(while循環):

另一種方法(遞歸):

2 基線條件和遞歸條件

def countdown(i):

print(i)

if i <= 0: # 基線條件

return

else: # 遞歸條件

countdown(i-1)

countdown(5)

3 棧

3.1 調用棧

def greet(name):

print('hello, ', name)

greet2(name)

print('getting ready to say bye...')

bye()

def greet2(name):

print('how are you, ', name)

def bye():

print('ok bye!')

greet('maggie')

3.2 遞歸調用棧

# 使用遞歸

def fact(x):

if x == 1:

return 1

else:

return x * fact(x-1)

print(fact(3))

# 使用循環

def fact2(x):

ans = 1

while (x > 1):

ans = ans * x

x = x - 1

return ans

print(fact2(3))

棧在遞歸中扮演著重要角色,使用棧雖然很方便,但是也要付出代價:存儲詳盡的信息可能戰勝大量的內存.每個函數調用都要戰勝一定的內存,如果棧很高,就意味著計算機存儲了大量函數調用的信息.在這種情況下,有兩種選擇:

使用循環

使用尾遞歸

4 小結

遞歸指的是調用自己的函數

每個遞歸函數都有兩個條件:基線條件和遞歸條件

棧有兩種操作:壓入和彈出

所有函數調用都進入調用棧

調用棧可能很長,這將占用大量的內存

總結

以上是生活随笔為你收集整理的递归 图 java,《算法图解》之递归的全部內容，希望文章能夠幫你解決所遇到的問題。

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