---

一、嵌套調(diào)用的過程

def show1():print("show 1 run start")show2()print("show 1 run end")def show2():print("show 2 run start")show3()print("show 2 run end")def show3():print("show 3 run start")print("show 3 run end")show1()

執(zhí)行結(jié)果

show 1 run start
show 2 run start
show 3 run start
show 3 run end
show 2 run end
show 1 run end

嵌套調(diào)用的過程圖解

函數(shù)一旦執(zhí)行結(jié)束，一會(huì)先回到調(diào)用處

二、遞歸的基本原則

1、遞歸的基本原則

遞歸函數(shù)通常遵循以下原則：

• 定義基本情況:確定一個(gè)或多個(gè)輸入的特殊情況，當(dāng)滿足這些條件時(shí)，遞歸函數(shù)將直接返回結(jié)果而不再調(diào)用自身。
• 減小問題規(guī)模:通過調(diào)用自身來解決一個(gè)規(guī)模更小的問題，這樣每次遞歸調(diào)用都在問題規(guī)模上取得了進(jìn)展。也就是需要一個(gè)已定義好的規(guī)則來使其它非基本的情況轉(zhuǎn)化為基本情況。
• 終止條件:遞歸函數(shù)必須包含能夠?qū)е潞瘮?shù)不再遞歸調(diào)用的條件，以避免無限遞歸。

2、無限遞歸調(diào)用

def show():print("show run start")show()print("show run end")show()

無限遞歸調(diào)用報(bào)錯(cuò)
RecursionError: maximum recursion depth exceeded while calling a Python object

3、正常遞歸調(diào)用

def show(n):print(f"show run start-{n}")if n<10:show(n+1)print(f"show run end-{n}")show(1)

遞歸函數(shù)同嵌套函數(shù)調(diào)用一樣：誰(shuí)調(diào)用的你，返回到調(diào)用處

show run start-1
show run start-2
show run start-3
show run start-4
show run start-5
show run start-6
show run start-7
show run start-8
show run start-9
show run start-10
show run end-10
show run end-9
show run end-8
show run end-7
show run end-6
show run end-5
show run end-4
show run end-3
show run end-2
show run end-1進(jìn)程已結(jié)束，退出代碼為 0

當(dāng)代碼執(zhí)行到24行時(shí)，先恢復(fù)show(9)的狀態(tài)
show(9)是由show(8)的調(diào)用的，先恢復(fù)show(8)的狀態(tài)
依次

與嵌套函數(shù)調(diào)用過程相比：嵌套函數(shù)是由多個(gè)函數(shù)完成的，遞歸是有1個(gè)函數(shù)完成的

4、階乘問題

def f(n):if n==0 or n==1:return 1return n*f(n-1)print(f(5))

執(zhí)行流程：

5 * f(4)
5 * (4 * f(3))
5 * (4 * (3 * f(2)))
5 * (4 * (3 * 2 * f(1))))
5 * (4 * (3 * 2 * 1))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120

5、力扣：231. 2 的冪

簡(jiǎn)單

給你一個(gè)整數(shù) n，請(qǐng)你判斷該整數(shù)是否是 2 的冪次方。如果是，返回 true ；否則，返回 false 。
如果存在一個(gè)整數(shù) x 使得 n == 2x ，則認(rèn)為 n 是 2 的冪次方。

示例 1：
輸入：n = 1
輸出：true
解釋：20 = 1

示例 2：
輸入：n = 16
輸出：true
解釋：24 = 16

示例 3：
輸入：n = 3
輸出：false
示例 4：
輸入：n = 4
輸出：true

示例 5：
輸入：n = 5
輸出：false

class Solution:def isPowerOfTwo(self, n: int) -> bool:def panduan(s):if s <= 0:return Falseelif s == 1:return Trueelif s == 2:return Trueelse:if s % 2 == 0:return panduan(s // 2)else:return Falsereturn panduan(n)

6、力扣面試題 08.05. 遞歸乘法

中等

遞歸乘法。 寫一個(gè)遞歸函數(shù)，不使用 * 運(yùn)算符， 實(shí)現(xiàn)兩個(gè)正整數(shù)的相乘?？梢允褂眉犹?hào)、減號(hào)、位移，但要吝嗇一些。
示例1:
輸入：A = 1, B = 10
輸出：10

示例2:
輸入：A = 3, B = 4
輸出：12
提示:
保證乘法范圍不會(huì)溢出

class Solution:def multiply(self, A: int, B: int) -> int:if B == 0:return 0return A + self.multiply(A, B - 1)r=Solution()
A=3
B=4
print(r.multiply(A, B))

執(zhí)行流程

3+multiply(3, 3)
6+multiply(3, 2)
9+multiply(3, 1)
12+multiply(3, 0)

7、力扣、326. 3 的冪

簡(jiǎn)單

給定一個(gè)整數(shù)，寫一個(gè)函數(shù)來判斷它是否是 3 的冪次方。如果是，返回 true ；否則，返回 false 。
整數(shù) n 是 3 的冪次方需滿足：存在整數(shù) x 使得 n == 3x

示例 1：
輸入：n = 27
輸出：true

示例 2：
輸入：n = 0
輸出：false

示例 3：
輸入：n = 9
輸出：true

示例 4：
輸入：n = 45
輸出：false

class Solution:def isPowerOfTwo(self, n: int) -> bool:def panduan(s):if s <= 0:return Falseelif s == 1:return Trueelif s % 3 != 0:return Falseelse:return panduan(s / 3)return panduan(n)r=Solution()
n=9
print(r.isPowerOfTwo(n))

8、力扣342. 4的冪

簡(jiǎn)單

給定一個(gè)整數(shù)，寫一個(gè)函數(shù)來判斷它是否是 4 的冪次方。如果是，返回 true ；否則，返回 false 。
整數(shù) n 是 4 的冪次方需滿足：存在整數(shù) x 使得 n == 4x

示例 1：
輸入：n = 16
輸出：true

示例 2：
輸入：n = 5
輸出：false

示例 3：
輸入：n = 1
輸出：true

class Solution:def isPowerOfTwo(self, n: int) -> bool:def panduan(s):if s <= 0:return Falseelif s == 1:return Trueelif s % 4 != 0:return Falseelse:return panduan(s // 4)return panduan(n)r=Solution()
n=1
print(r.isPowerOfTwo(n))