一. 課上代碼
#使用遞歸來(lái)求解階乘運(yùn)算
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1)
number = int(input("請(qǐng)輸入一個(gè)正整數(shù)："))
result = factorial(number)
print("%d的階乘是：%d" % (number, result))
#使用普通迭代來(lái)求fibonacci數(shù)列
def fibonacci(n):
n1 = 1
n2 = 1
n3 = 1
if n < 1:
print("Your input is wrong!")
return -1
while (n - 2) > 0:
n3 = n2 + n1
n1 = n2
n2 = n3
n -= 1
return n3
result = fibonacci(20)
if result != -1:
print(result)
#使用遞歸來(lái)求fibonacci數(shù)列
def fibonacci(n):
if n < 1:
print("輸入有誤渔彰！")
return -1
if n == 1:
return 1
elif n == 2:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
number = int(input("請(qǐng)輸入一個(gè)正整數(shù)："))
result = fibonacci(number)
if result != -1:
print(result)
#遞歸的缺點(diǎn)在于爬坑，如果n很大的情況下砂沛，計(jì)算會(huì)很慢
遞歸求解漢諾塔游戲
- 對(duì)于游戲的玩法渣淳，可以分解為三個(gè)步驟：
- 將前63個(gè)盤(pán)子從X移動(dòng)到Y(jié)上
- 將最底下的第64個(gè)盤(pán)子從X移動(dòng)到Z上
- 將Y上的63個(gè)盤(pán)子移動(dòng)到Z上
- 問(wèn)題一：將X上的63個(gè)盤(pán)子借助Z移動(dòng)到Y(jié)上
- 問(wèn)題二：將Y上的63個(gè)盤(pán)子借助X移動(dòng)到Z上
- 問(wèn)題一可以拆解為：
- 將前62個(gè)盤(pán)子從X移動(dòng)到Z上
- 將最底下的第63個(gè)盤(pán)子移動(dòng)到Y(jié)上
- 將Z上的62個(gè)盤(pán)子移動(dòng)到Y(jié)上
- 問(wèn)題二可以拆解為：
- 將前62個(gè)盤(pán)子從Y移動(dòng)到X上
- 將最底下的第63個(gè)盤(pán)子移動(dòng)到Z上
- 將X上的第62個(gè)盤(pán)子移動(dòng)到Y(jié)上
#遞歸求解漢諾塔游戲
def hanoi(n, x, y, z):
if n == 1:
print(x, '-->', z)
else:
hanoi(n - 1, x, z, y) #將前n-1個(gè)盤(pán)子從x移動(dòng)到y(tǒng)上
print(x, '-->', z) #將最底下的最后一個(gè)盤(pán)子從x移動(dòng)到z上
hanoi(n - 1, y, x, z) #將y上的n-1個(gè)盤(pán)子移動(dòng)到z上
n = int(input("請(qǐng)輸入漢諾塔的層數(shù)："))
hanoi(n, 'X', 'Y', 'Z')
二. 動(dòng)動(dòng)手
- 使用遞歸編寫(xiě)一個(gè)power()函數(shù)模擬內(nèi)建函數(shù)pow()歼指，即power(x, y)為計(jì)算并返回x的y次冪的值
def power(x, y):
if y:
return x * power(x, y - 1)
else:
return 1
print(power(2, 3))
- 使用遞歸編寫(xiě)一個(gè)函數(shù)寝凌，利用歐幾里得算法求最大公約數(shù)畔濒，例如gcd(x, y)返回值為參數(shù)x和參數(shù)y的最大公約數(shù)
def gcd(x, y):
if y:
return gcd(y, x % y)
else:
return x
print(gcd(4, 6))
- 使用遞歸編寫(xiě)一個(gè)十進(jìn)制轉(zhuǎn)換為二進(jìn)制的函數(shù)（要求采用取2取余的方式洋满，結(jié)果與調(diào)用bin()一樣返回字符串形式）
def Dec2Bin(dec):
result = ''
if dec:
result = Dec2Bin(dec // 2)
return result + str(dec % 2)
else:
return result
print(Dec2Bin(62))
- 寫(xiě)一個(gè)函數(shù)get_digits(n)晶乔，將參數(shù)n分解出每個(gè)位的數(shù)字并按順序存放到列表中。舉例：get_digits(12345) ==>[1, 2, 3, 4, 5]
#personal code
result1 = []
result = []
def Get_digits(n):
if n > 0:
result1 = n % 10
result.append(result1)
Get_digits(n // 10)
Get_digits(12345)
result.reverse()
print(result)
#Reference code
result = []
def Get_digits(n):
if n > 0:
result.insert(0, n % 10)
Get_digits(n // 10)
Get_digits(12345)
print(result)
- 使用遞歸編程求解一下問(wèn)題：有5個(gè)人坐在一起牺勾，問(wèn)第五個(gè)人多少歲正罢？他說(shuō)比第4個(gè)人大2歲。問(wèn)第4個(gè)人歲數(shù)驻民，他說(shuō)比第3個(gè)人大2歲翻具。問(wèn)第三個(gè)人，他說(shuō)比第二個(gè)人大兩歲回还。問(wèn)第二個(gè)人裆泳，他說(shuō)比第一個(gè)人大兩歲。最后問(wèn)第一個(gè)人柠硕，他說(shuō)是10歲工禾。請(qǐng)問(wèn)第五個(gè)人多大运提？
age = 0
def age(n):
if n == 1:
return 10
else:
return age(n - 1) + 2
print(age(5))
