递归

如果一个函数直接或间接调用它自己，我们便称之为递归函数。之所以讨论它，是因为递归是一种解决问题的有效方法，也是一种分治的思想，它针对特定的问题，这类问题在结构上可以进一步分解为相似的子问题。例如阶乘函数：

\( n! = (n-1)!*n \)

下面的代码计算斐波那契（Fibonacci）数列：

\( \begin{cases} fib(0)=0, \ fib(1) = 1 \\ fib(n) = fib(n-1) + fib(n-2), \ n >1 \end{cases} \)

// ch0207_1.dart
void main() {
  var n = 20;
  print('fib($n) = ${fib(n).$2}'); // Output: fib(20) = 6765
}

/// fib function returns (fib(n - 1), fib(n))
(int, int) fib(int n) {
  if (n <= 1) return (0, 1);
  var (a, b) = fib(n - 1);
  return (b, a + b);
}

又如使用辗转相除法，计算两个整数的最大公约数（最大公因数）：

\( gcd(a, b) = gcd(b, a\%b) \)

// ch0207_1.dart
void main() {
  var a = 234, b = 678;
  print('gcd($a, $b) = ${gcd(a, b)}'); // Output: gcd(234, 678) = 6
}

/// Greatest common divisor
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

NOTE: 辗转相除法

用较大数除以较小数，得到余数;

如果余数为0，则除数即为最大公约数（算法终止），否则转下一步;

用余数代替原来的除数，用原来的除数代替原来的被除数，转第1步。

递归与循环

有时，递归函数可以用循环来改写，例如：

/// Greatest common divisor (loop version)
int gcd2(int a, int b) {
  while (b != 0) {
    (a, b) = (b, a % b);
  }
  return a;
}

gcd2与gcd函数的功能一样，只不过使用了循环而非递归来实现。

从0开始学Dart

递归

递归与循环