javascript递归理解及实战

一、递归： 函数中调用函数自己，在使用递归的时候一定需要有结束递归的条件，否则就会变成死循环。

想要用递归必须知道两个条件：

1、递归出口(终止递归的条件) 2、递归表达式(规律)

技巧： 在递归中常常是将问题切割成两个部分(1和整体的思想)，这能够让我们快速找到递归表达式(规律)

二、递归和循环的区别

简单来说，循环是有去无回，而递归则是有去有回(因为存在终止条件)。 举个栗子，你用你手中的钥匙打开一扇门，结果去发现前方还有一扇门，紧接着你又用钥匙打开了这扇门，然后你又看到一扇们…但是当你开到某扇门时，发现前方是一堵墙无路可走了，你选择原路返回——这就是递归 但是如果你打开一扇门后，同样发现前方也有一扇们，紧接着你又打开下一扇门…但是却一直没有碰到尽头——这就是循环。

三、实例

1、递归案例:求一个数字各个位数上的数字的和

function getEverySum(x) { if(x<10){ return x; } //获取的是这个数字的个位数 return x % 10 + getEverySum( parseInt( x/ 10 ) ); } console.log(getEverySum(987654321)); // 45

2、平铺多维数组

let arr = [ [1,2,], 3 ,4, [5, [6, [7 ,8, [9]]]]] let temp = [] function digui(arr) { for (let i = 0; i< arr.length; i++) { // 判断是不是数组，若是数组就在进行递归 if (dataType(arr[i]) === 'array') { digui(arr[i]) } else { // 不是数组直接push 进去 temp.push(arr[i]) } } } digui(arr) console.log(temp); //  [1, 2, 3, 4, 5, 6, 7, 8, 9] // 判断数据类型 function dataType(obj) { let o = {} return o.toString.call(obj).slice(8,-1).toLowerCase() }

2、求和

// for 求10以内数字的和 var sum=0 for ( var i =0; i < 10 ; i++ ) { sum = sum + i; } console.log(sum ); // 45 // 递归实现n个数字的和 function getSum (x) { if ( x ==1 ) { return 1; } return x + getSum ( x - 1 ); } console.log(getSum( 10 - 1 )); // 45

3、获取数组中的最大值

let array = [1, 11,11,115,115]; console.log(getMax(array,0,array.length - 1 )); // 115 /** * 递归，找出数组最大的值 * @param arr数组 * @param left 左边界，第一个数 * @param right 右边界，数组的长度 * @return */ function getMax(arr, left, right) { // left数组第一个元素 // right赋值为array.length-1 // 如果该数组只有一个数，那么最大的就是该数组第一个值了 if (left === right) { return arr[left]; } else { let a = arr[left]; //找出整体的最大值 let b = getMax(arr, left + 1, right); if (a > b) { return a; } else { return b; } } }

4、汉诺塔玩法 // 汉诺塔的规则 // 有三根柱子，原始装满大小不一的盘子的柱子我们称为A，还有两根空的柱子，我们分别称为B和C(任选) // 最终的目的就是将A柱子的盘子全部移到C柱子中 // 移动的时候有个规则：一次只能移动一个盘子，小的盘子不能在大的盘子下面(反过来：大的盘子不能在小的盘子上面)

console.log("bar1-- 有三个盘"); towersofHanoi(3, 'bar1', 'bar2', 'bar3'); * 汉诺塔 * @param n n个盘子 * @param start 起始柱子 * @param transfer 中转柱子 * @param target 目标柱子 * function towersofHanoi( n, start, transfer, target) { //只有一个盘子，直接搬到目标柱子 if (n === 1) { console.log(start + "---->" + target); } else { //起始柱子借助目标柱子将盘子都移动到中转柱子中(除了最大的盘子) towersofHanoi(n - 1, start, target, transfer); console.log(start + "---->" + target); //中转柱子借助起始柱子将盘子都移动到目标柱子中 hanoi(n - 1, transfer, start, target); } }

5、冒泡排序递归写法

冒泡排序：俩俩交换，在第一趟排序中能够将最大值排到最后面，外层循环控制排序趟数，内层循环控制比较次数 以递归的思想来进行改造： 当第一趟排序后，我们可以将数组最后一位(right)和数组前面的数(left,right-1)进行切割，数组前面的数(left,right-1)看成是一个整体，这个整体又是和我们的初始目的(找出最大值，与当前趟数的末尾处交换)是一样的 递归出口：当只有一个元素时，即不用比较了：left === right let arrays = [2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 1] bubbleSort(arrays, 0, arrays.length - 1) console.log(arrays) // [1, 1, 2, 2, 3, 3, 4, 5, 5, 5, 6, 8, 9] function bubbleSort(arr, left, right ) { let temp; //如果只有一个元素了，那什么都不用干 if (left === right) { } else { for (let i = left; i < right; i++) { if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } //第一趟排序后已经将最大值放到数组最后面了 //接下来是排序"整体"的数据了 bubbleSort(arr, left, right - 1); } }