什么是递归？

2025年3月17日 | 阅读 3 分钟

Dart 递归是一种方法，其中一个函数将其自身作为其子程序调用。它用于通过将复杂问题分解为子部分来解决复杂问题。一个函数重复调用自身或递归调用，那么这个过程称为递归。

迭代器可以是解决问题的一种选择，但建议程序员使用递归来处理复杂问题，因为它是一种有效的解决问题的技术。它需要更少的时间和代码来评估相同的复杂任务。

递归对同一函数进行多次调用；但是，应该有一个基本情况来终止递归。

递归使用分而治之的技术来解决复杂的数学计算任务。它将大任务分解成小块。

不建议使用递归来解决所有类型的问题。但是，它最适合一些问题，例如搜索、排序、Inorder/Preorder/Postorder、树遍历和图算法的 DFS。但是，在使用递归时，必须小心实现；否则，它会变成无限循环。

递归中的基本条件是什么？

void main() {
   int factorial(int num){
   
  if(num<=1) { // base case
        return 1;
  else{
         return n*fact(n-1);
 }
}    
}
}

在上面的例子中，基本情况定义为 n<=1，并且可以通过更改为较小的值直到匹配基本情况来解决较大值的数字。

注意 - 递归函数中需要基本情况或有效的终止条件；否则，它将变成无限循环。

Dart 递归函数

递归函数与其他函数非常相似，但区别在于它会递归地调用自身。递归函数会重复多次，直到它返回最终输出。它允许程序员使用最少的代码解决复杂问题。

递归是如何工作的？

让我们通过一个给定数字的阶乘的例子来理解递归的概念。在下面的例子中，我们将计算 n 个数字的阶乘。它是乘法的级数，如下所示。

递归函数的特点

递归函数的特点如下。

递归函数是一种特殊形式的函数，其中函数调用自身。
需要有效的基本情况来终止递归函数。
由于堆栈开销，它比迭代慢。

让我们看一下递归语法

语法

void recurse() {
  //statement(s)
 recurse();
//statement(s);
}
void main(){
   //statement(s)
  recurse();
 //statement(s)
}

让我们理解下面的例子。

示例 - 1

int factorial(int num){
  
  //base case of recursion. 
  if(num<=1) { // base case
        return 1;
}
  else{
         return num*factorial(num-1);    //function call itself.
 }
}
void main() {
  var num = 5;
  // Storing function call result in fact variable.
  var fact = factorial(num);
  print("Factorial Of 5 is: ${fact}");
}

输出

Factorial Of 10 is: 120

说明

在上面的例子中，factorial() 是一个递归函数，因为它调用了自身。当我们通过传递整数值 5 来调用 factorial() 函数时，它将通过递减数字来递归调用自身。

factorial() 函数将每次被调用，直到它匹配基本条件或它等于 1。它将数字与该数字的阶乘相乘。考虑以下递归调用的解释。

factorial(5)              # 1st call with 5
* factorial(4)          # 2nd call with 4
* 4 * factorial(3)      # 3rd call with 3
* 4 * 3 * factorial(2)  # 4th call with 2
* 4 * 3 * 2 * 1         # return from 2nd call
                  # return from 1st call

当数字减少到 1 时，递归结束，这是递归的基本条件。

递归函数必须有一个基本条件以避免无限调用。