9.5 递归函数+常见算法

2025-10-24 06:47:34 世界杯冠军最多

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

递归：

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

好处

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

创建一个简单的递归

直接调用的递归

// 直接调用；自己调用自己； 死递归

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 = n

for(var i=n-1; i>=1; i--){

result *= i

}

return result

}

console.log(sum(10));

function sum(n){

result = 0

// 5

for(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 += '

    '

    for (let i = 0; i < data.length; i++) {

    html +=

    `

  • html += data[i].title

    if (data[i].cont) {

    html += createMenu(data[i].cont)

    }

    html +=

    • `

    }

    html += '

'

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

// for(j=0;j

for(j=0;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

//1、默认第一个数字位最小数

var min = arr[i]; // 第一个值位最小值

var index = i; //保存最小值的下标

// 循环到底

for(var j=i+1;j

if(arr[j]

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