| 🔥「深入本质」一篇文章彻底理解递归 | 您所在的位置：网站首页 › 递归的过程是 › 🔥「深入本质」一篇文章彻底理解递归 |
🔥「深入本质」一篇文章彻底理解递归
|
"递归"是所有语言都有的一种常用操作，但是你真的用好递归了吗？对递归没有任何疑问了吗？觉得递归总是找不到感觉不知道该怎么写吗？这篇文章正是为此而生的 递归的本质就是函数调用而已，深入理解背后的原理你能轻松用好它 本文将包含以下内容 什么是递归 如何选择停止条件 递归的本质、递归是如何工作的 面试题、递归应用实例 快速介绍递归是所有语言都很常见的特性，也是我们解决很多问题的利器，那么，什么是递归？ //最简单的理解，递归就是一个函数调用它自己 function blueFn(){ blueFn(); } blueFn();当然，程序不能真的像上面那样写，不然函数会无止境的调用下去，最后只能报错 顺便一说，这个错误是“栈溢出”引起的，后面咱们会详细说这个问题，先继续往下看 递归的终止程序中任何操作都不能无穷无尽的执行下去，递归也不例外，所以递归一定要有一个适当的**“终止条件”**——也就是说，到此为止不会再产生新的调用，看个例子——假设我们想求一个n的阶乘，也就是5!=5*4*3*2*1这种小学都做过的东西 function N(num){ //5! = 5 * 4! return num*N(num-1); } N(5);但这个程序不会正确终止，只会报错，和上面一样 为什么？因为这个函数永远会继续往下调用，但我们知道1!其实就“到头了”，因为1!=1，所以我们完全可以用1作为终止条件 function N(num){ if(nummaxR) return maxL; else return maxR; }上面的例子中，我们并没有正面解决问题，反而采取了“逃避”的办法——递归本质上就是问题的划分和结果的合并 把问题划分为更小的问题 let arrL=arr.slice(0, arr.length/2); let arrR=arr.slice(arr.length/2, arr.length);分别求解 let maxL=findMax(arrL); let maxR=findMax(arrR);把结果合并起来 if(maxL>maxR) return maxL; else return maxR; 递归是怎么执行的首先，假设我们有一组数据[12, 8, 96, 27, 3, 9, 81] 第一部分、分割 第1次，我们会把它分成两部分：[12, 8, 96, 27]和[3, 9, 81] 并且，带来两个新的函数调用findMax([12, 8, 96, 27])和findMax([3, 9, 81]) 然后，每个数组都会被进一步划分为两部分，直到不可再分为止第二部分、合并 每次，findMax都会将两边的结果（例如：12和8）进行比较，并将其中较大的作为结果 重复这个过程，直到所有函数返回，既能得到最终结果 递归的本质、停止条件开始时我们就说过，递归需要明确的终止条件，否则会出现无限调用引发栈溢出的问题，那么我们有两个问题： 为什么会栈溢出？什么是栈溢出？它咋就溢出了 我们应该如何选择终止条件？ 递归的本质递归其实并不特殊，它依然是函数调用，只不过是自己调用自己（更专业的说法，函数是“可重入的”），所以理解递归最好的办法是先理解函数是如何工作的 函数调用栈js和所有语言一样，内存中有一块专门存放函数调用的空间，称为“函数调用栈”，当我们调用函数或声明局部变量时，都是在操作它 直接看个程序吧，我们来看看它是怎么执行的 function blueFn(num){ return sum(12, 5)+num; } function sum(a, b){ return a+b; } let res=blueFn(99); console.log(res+8);第一步、它会从第9行开始执行，这时栈是空的 第二步，开始调用blueFn，这时会在栈上存储参数、返回位置等信息，并转到函数内部执行 第三步，碰上了新的函数调用sum(12, 5)，又进去一层 第三步，完成a+b的运算，并按照栈的要求返回，然后清理栈的信息 第四步，完成17+num的运算并返回，当然，也会清理栈的信息 最后，完成console.log(116+8)，整个程序结束 在这个过程中，我们能看到3点： 函数的调用通过栈完成 函数的参数、局部变量、pc指针等，通过栈传递 函数调用层级越深，栈存储的东西越多 栈的上限计算机的资源是有上限的，js引擎为了保护自身的运行，不会允许你无限的往栈上放东西，所以函数栈有一个上限（不同语言不一样，但都不是很大），当然，这样做其实并不会对你有太多影响，因为程序正常时，栈的空间绝对够用 这种保护机制也能顺便帮我们找到错误的递归，总体而言是个有益的设定，那么下一个问题就是，我们如何选择合适的停止条件，确保我们的程序能正确的执行呢？ 面试题、实例 题目1-数组的反转有这样一个题目，要求大致是不用循环、不用reverse、不用这不用那反正就是各种疯狂暗示，让你用递归来解决，咱们就来试一下 let arr=[1,2,3]; function reverse(a){ //在这里具体写东西 } reverse(arr); //希望得到反转后的[3,2,1]先不着急写哈，我们来分析一下，既然要用递归，那么想清楚怎么用 [1,2,3] -> [3,2,1] //我们可以看做 1 和 [2,3] -> [3,2] 和 1 //也就是说 arr[0] + arr[1...n] -> reverse(arr[1...n]) + arr[0]有了这个思路，其实是非常容易完成的 let arr=[1,2,3]; function reverse(a){ if(a.length |
【本文地址】