当前位置：首页 > web >正文

9.5 递归函数+常见算法

web 2025/9/7 12:37:02

导语：有个很经典的故事：从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事！故事是什么呢？『从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事！故事是什么呢？』……

递归：

如果一个函数在内部调用自身本身，这个函数就是递归函数

好处

递归函数最大的好处在于可以精简程序中繁杂，重复调用程序

创建一个简单的递归

直接调用的递归

// 直接调用；自己调用自己； 死递归
function fun(){console.log('from func');fun();
}
fun()

间接调用的递归

// 间接调用自己
function foo(){console.log('from foo');bar();
}
function bar(){console.log('from bar');foo();
}
foo()

![[1280X1280 (5).PNG]]
实现递归；递归要有最终的一个出口

// 递归的实现
function age(n){// 测试数据console.log(n);if(n==1){console.log(18);return;}return age(n-1);
}
age(5);

总结：递归只是一种思想，只不过在程序，依靠函数自身嵌套来实现

使用递归求阶乘

案例：求1 * 1+ 2 * 2+ 3 * 3+ 4 * 4…的和

普通写法

function sum(n){result = nfor(var i=n-1; i>=1; i--){result *= i}return result
}
console.log(sum(10));function sum(n){result = 0// 5for(var i=n; i>=1; i--){result += i * i // result = 0 + 5*5}return result}

递归

function sum(n){if(n==0){return 0;}else{return n*n + sum(n-1);}
}
console.log(sum(5));

总结：递归的好处是递归函数常用于检索大量数据，比如检索一个拥有300万个数的列表，从中查找某个数是否存在，如果用for遍历，会严重占用计算机计算能力，那么我们可以通过递归函数来减少搜索量。

递归实现的特点

有进有出
![[1715a592-8e0e-4f9f-bbda-a328ac188906.png]]

递归可以将复杂的程序变简单
需求：如计算数字1+到100，判断数字是否小与100，判断变量是否小与100，小于100让他+1，然后输出当前变量i，直到100

// 普通写法
var i=0;
function test(i){i+=1;console.log(i);if(i<100){i+=1;console.log(i);if(i<100){i+=1;console.log(i);}}
}
test(i);
// 改成递归函数
var i=0;
function test(i){i+=1;console.log(i);if(i<100){test(i);}
}
test(i);

递归只是一种思想，只不过在程序，依靠函数自身嵌套来实现（递归使用的是压栈，弹栈，枪压子弹，叠书）

思考

function func(n){console.log(n);if(n>0){func(n-1);}else{console.log(' ');}console.log(n);
}
func(3);

案例：计算1到100之间相加之和；通过循环和递归两种方式实现

// 普通写法
function sum_cycle(n){sum=0;for(var i=1;i<=n;i++){sum+=i}console.log(sum);
}
sum_cycle(5);
// 递归写法
function sum_cycle(n){if(n>0){return n + sum_cycle(n-1);}else{return 0;}
}
console.log(sum_cycle(5));

案例：小熊掰玉米

案例：小熊掰玉米一天小熊来到一片玉米地，兴奋的掰了若干个玉米，他发现太多了，于是扔了其中一半，感觉还是有点多，于是又扔了一个后往家赶；当它走了一米的时候感觉有点累，于是扔掉其中的一半加一个，继续往前每走一米重复以往的动作，扔掉其中的一半加一个；当它走到10米时候，发现手中就剩一个了，有点伤感，也忘了开始自己摘了几个玉米了，那么你帮小熊算算，它开始掰了多少个玉米？

分析：小熊掰玉米，给定的是总的米数，但是获取10米需要依赖于9米，求9米，需要依赖8米…以此类推，所以想要获取10米的需要知道没走的时候，0米的时候手里有几个玉米

function getTotle(length){if(length == 0){return 1;}else{return 2*(getTotle(length-1)+1);}
}
console.log(getTotle(10));

递归的特点：函数内部调用函数本身有进有出必须有出口每次调用函数都会用掉一点内存，在足够多次数的函数调用发生后（在之前的调用返回后），空间就不够了，程序会以一个“超过最大递归深度”的错误信息结束。

面试题：

var a = 10;
function show() {console.log(a); // 结果？a = 5;console.log(window.a); // 结果？var a = 20;console.log(a); // 结果？
}
show();

用递归实现多层数据的渲染

function createMenu(data) {let html = ''html += '<ul>'for (let i = 0; i < data.length; i++) {html += `<li>html += data[i].titleif (data[i].cont) {html += createMenu(data[i].cont)}html += </li>`}html += '</ul>'return html
}
let html = createMenu(foodData.data)
document.write(html)

冒泡排序

冒泡排序：依次比较相邻的两个值，如果后面的比前面的小，则将小的元素排到前面。依照这个规则进行多次并且递减的迭代，直到顺序正确。
![[db9509e8-4a2b-4a39-bfcf-d63aa4098ba4.png]]

var examplearr=[8,94,15,88,55,76,21,39];
function sortarr(arr){for(i=0;i<arr.length-1;i++){// for(j=0;j<arr.length-1-i;j++){ //更节省内存for(j=0;j<arr.length-1;j++){if(arr[j]>arr[j+1]){var temp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}}return arr;
}

选择排序

![[25cf7f81-8f61-49f0-a341-24431a21d6f9.png]]

var arr=[5,3,7,1,2,8];
// 一共找出五个最小的数，最后一个不用管了，所以，六个数，循环5次。
for(var i=0;i<arr.length-1;i++){//1、默认第一个数字位最小数var min = arr[i]; // 第一个值位最小值var index = i; //保存最小值的下标// 循环到底for(var j=i+1;j<arr.length;j++){if(arr[j]<min){min = arr[j];index = j;}}//2、交换(数组中的最小数和arr[i])var t = arr[i]; arr[i] = arr[index];arr[index] = t;
}
console.log(arr);

冒泡排序和选择排序对比

一般情况下对比两个算法的好坏，会从时间复杂度和空间复杂度两个方面进行对比；

时间复杂度：指的是一个算法执行所耗费的时间。
空间复杂度：指运行完一个程序所需内存的大小。

// 生成1000个数字进行排序
// 1. 创建空数组，保存随机出来的数据
var getarr = [];
// 2. 获取随机数字
for(var i=0; i<100000; i++){var num = Math.round( Math.random()*1000 );getarr.push( num );
}
// 3. 获取当前时间
var oDate = new Date();
// 4.调用选择排序或者冒泡排序
xuanze(getarr); // 10W - 10m
// maopao(getarr); // 10W - 13354m
// 5. 获取时间差值
o.innerHTML = new Date() - oDate;

二分查找法

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

function binary_search(num,list){var low = 0; // 获取开始位置var height = list.length-1; // 获取结束位置，下标值while(low <= height){ // 判断数组中是否有值mid = parseInt((low + height)/2); // 获取数组中的中间值if(list[mid] == num){ // 判断正好是中间值，返回下标return mid; //}else if(list[mid] > num){ // 如果中间值 > 输入的数字，表示在左半部分height = mid -1}else{low = mid + 1; // 如果中间值 < 输入的数字，表示在右半部分}}return -1; // 没找到
}

https://www.cnblogs.com/ranyihang/p/16128154.html

查看全文

http://www.xdnf.cn/news/20229.html