2020.12.01
什麼是遞迴?
遞迴在程式語言中是相當重要的,尤其是要使用或設計演算法時常會用到,那什麼是遞迴?
遞迴(英語:recursion)在電腦科學中是指一種通過重複將問題分解為同類的子問題而解決問題的方法。遞迴式方法可以被用於解決很多的電腦科學問題,因此它是電腦科學中十分重要的一個概念。 絕大多數程式語言支援函式的自呼叫,在這些語言中函式可以通過呼叫自身來進行遞迴。 by wiki
Recursion means ‘a function calling itself inside the function’
Peter:所謂的遞迴函式,就是一個會call自己的函式
遞迴就像是個迴圈,他會不斷地跑。
遞迴數列?
遞迴數列如常見的
等差數列(每一項n的值都是n-1的值加上某個數量)。
等比數列與(每一項n的值都是n-1的值呈上某個數量)。
與非常有名的 費波那契數(Fibonacci number)
前提為第0個和第1個數字為1,每個數字是兩個前述者的總和,形成了這個數列。大概會長這樣
[1,1,2,3,5,8,13,21,34,55............n]
若是要寫一個function,輸入n,要輸出第n個的值,就能用遞迴寫出來
遞迴演算法(Recursive Algorithm)
在使用遞迴言算法時,數學歸納法必須先理解(汗,高中數學都忘光了)
數學歸納法:假設有一個關於正整數n的命題,如要證明他對每個正整數n都成立,可以依循兩個步驟
1.起始步驟:當n=1時,檢驗命題成立
2.歸納步驟:當n=k時命題成立,推導出n=k+1時命題亦成立排好的骨牌
1.起始步驟:第一塊骨牌會倒(成立)
2.歸納步驟:當地N塊倒了,第N+1塊(他的下一塊)也會倒得證明:骨牌會全倒
寫一個算等差級數合的fucntion(給定6,丟出1到6的總和)
function cal(number)
{ //第一種作法 等比級數公式
return(1+number)*number/2
//第二種做法 迴圈
let result=0;
for(let i=0;i<number,i++){result+=(i+1)}
return result;
//第三種作法 遞迴
if(number===1){return 1}
return number+cal(number-1)
}