让我们了解 JS 中的递归：类型、时间复杂度

在文章实战开发的过程中，我们经常会遇到一些这样那样的问题，然后要卡好半天，等问题解决了才发现原来一些细节知识点还是没有掌握好。今天golang学习网就整理分享《让我们了解 JS 中的递归：类型、时间复杂度》，聊聊，希望可以帮助到正在努力赚钱的你。

目录

• 什么是递归？
• 头递归
• 尾递归
• 树递归
• 间接递归

什么是递归？

函数调用自身的过程称为递归，负责的函数称为递归函数。

递归类型：
从高层次来看，有四种类型

• 头递归： 在这里，递归函数在检查基本条件之后和执行任何逻辑之前立即调用自身。

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 中的递归：类型、时间复杂度》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！