[課後作業] 第022講：函數：遞歸是神馬|課後測試題及答案

[課後作業] 第022講：函數：遞歸是神馬|課後測試題及答案 

 

《零基礎入門學習Python》視頻下載地址：傳送門

   
測試題：
      
0.遞歸在編程上的形式是如何表現的呢？


1.遞歸必須滿足哪兩個基本條件？


2.思考一下，按照遞歸的特性，在編程中有沒有不得不使用遞歸的情況？


3.用遞歸去計算階乘問題或斐波那契數列是很糟糕的算法，你知道為什麼嗎？


4.請聊一聊遞歸的優缺點（無需官方陳詞，想到什麼寫什麼就可以）


5.拿手機拍一張“遞歸自拍照片”


動動手：
     
0.使用遞歸編寫一個power()函數模擬內建函數pow()，即power(x, y)為計算並返回x的y次冪的值。


1.使用遞歸編寫一個函數，利用歐幾里得算法求最大公約數，例如gcd(x, y)返回值為參數x和參數y的最大公約數。


2.請寫下這一節課你學習到的內容：格式不限，回憶並複述是加強記憶的好方式

回复您的答案即可查看參考答案！

      
測試題答案：
   

本帖隱藏的內容

0.遞歸在編程上的形式是如何表現的呢？

答：在編程上，遞歸表現為函數調用本身這麼一個行為。

舉個例子（遞歸求階乘）：

1. def factorial(n):
2.     if n == 1:
3.         return 1
4.     else:
5.         return n * factorial(n-1)
6. 
   
7. number = int(input('請輸入一個整數：'))
8. result = factorial(number)
9. 
   
10. print("%d的階乘是：%d" % (number, result))

複製代碼

1.遞歸必須滿足哪兩個基本條件？

答：

一、函數調用自身

二、設置了正確的返回條件


2.思考一下，按照遞歸的特性，在編程中有沒有不得不使用遞歸的情況？

答：例如漢諾塔，目錄索引（因為你永遠不知道這個目錄裡邊是否還有目錄），快速排序（二十世紀十大算法之一），樹結構的定義等如果使用遞歸，會事半功倍，否則會導致程序無法實現或相當難以理解。


3.用遞歸去計算階乘問題或斐波那契數列是很糟糕的算法，你知道為什麼嗎？

答：小甲魚在課程的開頭說“普通程序員用迭代，天才程序員用遞歸”這句話是不無道理的。

但是你不要理解錯了，不是說會使用遞歸，把所有能迭代的東西用遞歸來代替就是“天才程序員”了，恰好相反，如果你真的這麼做的話，那你就是“烏龜程序員”啦。

為什麼這麼說呢？不要忘了，遞歸的實現可以是函數自個兒調用自個兒，每次函數的調用都需要進行壓棧、彈棧、保存和恢復寄存器的棧操作，所以在這上邊是非常消耗時間和空間的。

另外，如果遞歸一旦忘記了返回，或者錯誤的設置了返回條件，那麼執行這樣的遞歸代碼就會變成一個無底洞：只進不出！所以在寫遞歸代碼的時候，千萬要記住口訣：遞歸遞歸，歸去來兮！出來混，總有一天是要還的！


4.請聊一聊遞歸的優缺點（無需官方陳詞，想到什麼寫什麼就可以）

答：

優點：

1）遞歸的基本思想是把規模大的問題轉變成規模小的問題組合，從而簡化問題的解決難度（例如漢諾塔遊戲）。

2）有些問題使用遞歸使得代碼簡潔易懂（例如你可以很容易的寫出前中後序的二叉樹遍歷的遞歸算法，但如果要寫出相應的非遞歸算法就不是初學者可以做到的了。）

缺點：

1）由於遞歸的原理是函數調用自個兒，所以一旦大量的調用函數本身空間和時間消耗是“奢侈的”（當然法拉利也奢侈，但還是很多人趨之若鶩）。

2）初學者很容易錯誤的設置了返回條件，導致遞歸代碼無休止調用，最終棧溢出，程序崩潰。


5.拿手機拍一張“遞歸自拍照片”

動動手答案：

本帖隱藏的內容

0. 使用遞歸編寫一個power() 函數模擬內建函數pow()，即power(x, y) 為計算並返回x 的y 次冪的值。

1. def power(x, y):
2.     if y:
3.         return x * power(x, y-1)
4.     else:
5.         return 1
6.    
7. print(power(2, 3))

複製代碼

1. 使用遞歸編寫一個函數，利用歐幾里得算法求最大公約數，例如gcd(x, y) 返回值為參數x 和參數y 的最大公約數。

1. def gcd(x, y):
2.     if y:
3.         return gcd(y, x%y)
4.     else:
5.         return x
6.    
7. print(gcd(4, 6))

複製代碼

2.請寫下這一節課你學習到的內容：格式不限，回憶並複述是加強記憶的好方式！

小甲魚希望你認真對待作業就像你希望小甲魚推出高質量視頻一樣渴望^_^

（1）什麼時候遞歸

有調用函數自身的行為

有正確的返回條件

（2）遞歸求階乘

寫一個求階乘的函數：

首先看不用遞歸的程序：

def factorial(n):








 if n ==0 or n == 1:








  result = 1








  return result








 else:








  result = n








  for i in range(1,n):








   result *= i








  return result

然後使用遞歸實現：

def factorial(n):








 if n == 1 or n == 0:








  return 1








 else:








  return n * factorial(n-1)