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

递归是函数调用自身的过程，递归函数负责执行这一过程。 递归的类型包括头递归、尾递归、树递归和间接递归。

头递归：递归函数在检查基本条件之后和执行任何逻辑之前立即调用自身。例如，函数 getsquares(n) 在 n > 0 的条件下，先调用自身 getsquares(n-1)，然后执行 console.log(n*n)。这种递归方式会导致输出按升序排列。其时间复杂度为 O(n)。
尾递归：递归函数在执行完所有逻辑后调用自身并结束。例如，函数 getsquares(n) 在 n == 0 时返回，否则先执行 print(n * n)，然后调用 getsquares(n - 1)。这种递归方式会导致输出按降序排列。其时间复杂度同样为 O(n)。
树递归：递归函数在同一条件下多次调用自身。例如，函数 dosomething(n) 在 n <= 2 时返回 n，否则返回 dosomething(n - 1) + dosomething(n - 2)。这种递归方式在图中会形成树状结构，因此称为树递归。其时间复杂度为 O(2^n)。
间接递归：递归函数 a 调用递归函数 b，函数 b 再调用递归函数 a，形成循环调用。例如，函数 doSomethingA(n) 和 doSomethingB(n) 相互调用，直到满足基本条件。这种递归方式称为间接递归。其时间复杂度取决于具体的实现和调用次数，通常需要通过分析递归调用的次数和深度来确定。

热门标签