1 什么是遞歸?
- 先遞進(jìn),再回歸.
2 遞歸三大要素
- 明確函數(shù)想要什么?
- 尋找遞歸結(jié)束條件.
- 找出函數(shù)的等價(jià)關(guān)系式(規(guī)律).
3 實(shí)例
3.1 階乘
- 在數(shù)學(xué)中黄锤，正整數(shù)的階乘是所有小于及等于該數(shù)的正整數(shù)的積
-
1! = 1遞歸結(jié)束條件 -
2! = 2*1---> 2! = 2 * 1! 找出函數(shù)的等價(jià)關(guān)系式 -
3! = 3*2*1---> 3! = 3 * 2! 找出函數(shù)的等價(jià)關(guān)系式 -
4! = 4*3*2*1---> 4! = 4 * 3! 找出函數(shù)的等價(jià)關(guān)系式
function factorial(n) {
if (n === 1) {
return 1;
}
return n * factorial(n - 1);
}
3.2 斐波那契數(shù)列
- 指的是這樣一個(gè)數(shù)列：0慎颗、1局义、1、2、3、5夹纫、8、13设凹、21舰讹、34...
- 從第三個(gè)數(shù)開始,等于前2個(gè)數(shù)的和.
- f(0) =0,
- f(1)=1,
- f(2)=1 ---> f(0)+f(1)
- f(3)=2, ---> f(1)+f(2)
- f(4)=3, ---> f(2)+f(3)
- f(5)=5 ---> f(3)+f(4)
function Fibonacci(n) {
if (n === 0) {
return 0;
}
if (n === 1 || n === 2) {
return 1;
}
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
3.3 小青蛙跳臺(tái)階
- 一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)闪朱。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法月匣。
- n為臺(tái)階總數(shù)
- f(1)=1 臺(tái)階為1時(shí),只有1種跳法
- f(2)=2 臺(tái)階為2時(shí),只有2種跳法
- f(3)拆解成 f(2)+f(1) --->3
- f(4)= f(3)+f(2) --->5
- 我們發(fā)現(xiàn)這就是斐波那契數(shù)列
function jump(n) {
if(n<=2){
return n;
}
return jump(n - 1) + jump(n - 2);
}
本文資源來源
對(duì)于遞歸有沒有什么好的理解方法钻洒？ - 方應(yīng)杭的回答 - 知乎
https://www.zhihu.com/question/31412436/answer/738989709
對(duì)于遞歸有沒有什么好的理解方法？ - 帥地的回答 - 知乎
https://www.zhihu.com/question/31412436/answer/683820765
