第九章 递归

自我测试

本篇文章的测试用例及调试方法见前言

说明

递归是一种解决问题的方法,他从解决问题的各个小部分开始,直到解决最初的大问题.递归通常涉及函数调用自身.

const test = (i) => {     console.log(i)     test(++i);   } 

这是一种明显的递归,自己调用自己

function test2(i){     console.log("test2: " + i++)     test(i) }  function test(i){     console.log("test: " + i++)     test2(i) }   

这个也是一种递归,通过两个方法之间的相互调用,然后实现递归.但是这种代码我们一般是不会直接拿去运行的.为什么呢???

相信你也看出来了,上面的递归写法有问题,我调用我自己,然后自己调用自己,然后自己又调用了自己......,形成了一个闭环,所以递归的最重要的一个点出现了 基线条件(跳出循环的条件)

调用栈(这个对后面分析递归很重要)

每当一个函数被一个算法调用时,该函数会进入调用栈的顶部.当使用递归的时候,每个函数调用都会堆叠在调用栈的顶部,这是因为每个调用都可能依赖前一个调用的结果

尾部调用优化(ES2015新知识点)

案例

let i = 0; function recursiveFn(){     i++; 	recursiveFn(); } try{     recursiveFn(); }catch(ex){     console.log(ex) } 

如果函数内的最后一个操作是调用函数(如案例),会通过"跳转指令"(jump)而不是"子程序调用"(subroutine call)来控制.也就是说,在ES2015中,这里的代码可以一直执行下去.因此,具有停止递归的基线条件非常重要尾调用优化更多信息

练习

阶乘

说明:

5的阶乘: 5 * 4 * 3 * 2 * 1

9的阶乘: 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

代码

function recursionFactorial(num: number): number {     //找到结束条件     if (num === 1) {         return 1;     }     return num * recursionFactorial(num - 1); } 

还是一定要找到 基线条件,这个是递归的必要条件,不然你的程序会死循环,然后卡死

图解

是否还喜欢这种图解,如果喜欢,可以进入下一篇章第十章 树,带你走进树的遍历

斐波那契数列

说明

0 1 1 2 3 5 8 13 21 34 ....

第1个数: 0

第2个数: 1

第3个数 = 第2个数 + 第1个数

第4个数 = 第2个数 + 第3个数

第5个数 = 第4个数 + 第3个数

........

图解

代码

/*求n个斐波那契数的和*/ function newRecursionSequence(n: number): number {     if (n === 0) return 0;     if (n <= 2) return 1     return newRecursionSequence(n - 1) + newRecursionSequence(n - 2); } 

优化版代码

function newNewRecursionSequence(n: number) {     let memo: Array<number> = [0, 1];     let fbnc = (n: number): number => {         if (memo[n] != null) return memo[n];         //新算出的值保存在memo数组里         return memo[n] = fbnc(n - 1) + fbnc(n - 2);     }     return fbnc(n); } 

优化版对比第一版好在对数据进行了缓存,这样就不用反复的计算数据(图解中可以看到我们反复计算了n为 3 ,2等时的值)