目录
什么是递归？头递归尾递归树递归间接递归
什么是递归？
函数调用自身的过程称为递归，负责的函数称为递归函数。
递归类型：
从高层次来看，有四种类型
头递归： 在这里，递归函数在检查基本条件之后和执行任何逻辑之前立即调用自身。
function getsquares(n){ if(n>0){ getsquares(n-1); console.log(n*n); return; } }getsquares(3)
登录后复制
n = 3 的输出是：1 4 9
如果您注意到了，我们正在打印数字的平方，然后通过将数字减 1 来调用该函数。
因此您将按升序排列所有方块。
但是，如果您为尾递归编写相同的逻辑，您将按降序获得输出。上述代码的时间复杂度将是 o(n+1) 即 o(n).
尾递归：递归函数调用自身和结束，即执行完所有逻辑后。
function getsquares(n) { if (n == 0) return; print(n * n); getsquares(n - 1);}getsquares(3)
登录后复制
n=3 的输出是： 9 4 1
时间复杂度是o(n+1)即o(n).
树递归：递归函数在同一条件下多次调用自身。
function dosomething(n) { if (n <= 2) return n; return dosomething(n - 1) + dosomething(n - 2);}console.log(dosomething(5))
登录后复制
n=5 的输出是：8
如果您在图中注意到，我们以树状格式调用 self 函数，这就是为什么我们称这种类型为树递归.
时间复杂度为 o(2^(n+1)+1) 即 o(2^n).
间接递归 ：递归函数a调用递归函数b，函数b调用递归函数a。所以，你就明白为什么我们称之为间接递归了。
function doSomethingA(n) { if (n <= 2) return n; return doSomethingB(n - 1)}function doSomethingB(n) { if (n <= 2) return n; return doSomethingA(n - 1)}console.log(doSomethingA(5))
登录后复制
n=5 的输出是：2
说实话，这个例子没有太多逻辑，我举这个例子只是为了向你解释这个概念。
如果您注意到我们正在调用 dosomethinga() 并且 dosomethinga 正在调用 dosomethingb() 函数，并且进一步 dosomethingb 正在调用 dosomethinga() 函数。
这种类型的递归调用称为间接递归。
问你的问题：
尝试计算间接递归的时间复杂度。如果您有任何疑问或者不明白的地方，可以通过写评论来询问，我会尽力通过解释来解决。
以上就是让我们了解 JS 中的递归：类型、时间复杂度的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2670850.html
