一厅瞎、 遞歸的寫法套路
斐波那契數(shù)列
形如 1,1,2,3,5,8,13,21,34......這樣的數(shù)列，某個位置的數(shù)字等于它前面兩項數(shù)字的和
求斐波那契數(shù)列第 n 項的值的代碼如下：
function fib(n){
if(n ===1 || n === 2){
return 1
} else{
return fib(n-1) + fib(n-2)
}
}
console.log(fib(6)) // 8
結(jié)果證明是對的
求階乘
代碼如下
function fac(n){
if(n ===1 || n === 0){
return 1
} else{
return n * fac(n-1)
}
}
console.log(fac(5)) // 120
套路如下
-
找規(guī)律：找用一個公式可以總結(jié)出的規(guī)律
像遞歸的規(guī)律比較好找斥铺，等于前兩項的和就行了，而且用公式也比較好表達
但是階乘的常見的規(guī)律不是比較好用公司來總結(jié)缔莲，因為它是等于前 n 項的的乘積
但是他還有一個通式 是 百度可得
image.png
明顯第二個可以用公式表達出來
- 找出口：整個數(shù)列會有一個確定的值复斥，其他的值都是根據(jù)這個值和規(guī)律算出來的
- 像上面一樣寫if ...else ...
二、 call stack
stack是棧的意思澄步，看上面的函數(shù)的執(zhí)行過程冰蘑，實際上每一次運算，前面的所有的值都在“等著后面的結(jié)果”村缸，每當函數(shù)運行一次祠肥，都會call stack一下，而且因為stack 是遵循先入后出的梯皿，就是最先進去的運算（或者過程）最后出來仇箱，當需要算的值比較大的時候县恕，stack 里面的位置就可能會不夠用，就會出現(xiàn)錯誤工碾。
因此弱睦，一般不要用 遞歸來進行計算，而且一般的遞歸都可以用循環(huán)來解決
有機會會更新一下用循環(huán)的寫法來進行上面的運算
