2. 编写递归函数¶

2.1. 编写递归函数¶

递归地求解一个"大"问题，意思是先求解该问题的一个或多个更小规模的版本，再用这些小问题的解来求解"大"问题。具体来说，递归求解问题意味着问题的小规模版本也以类似的方式来求解。例如，考虑对数组中的值求和的问题。对数组的前 50 个元素求和与对前 100 个元素求和有什么区别？你会使用同样的方法。你甚至可以借助小问题的解来帮助求解大问题。

下面是编写任何递归函数都需要的四个基本步骤。

Settings

Saving...

Server Error
Resubmit

现在我们来看看用递归方式编写 Sum 的几种不同写法。

Settings

Saving...

Server Error
Resubmit

Example 8.2.1

我们前面那个对数组前 \(n\) 个数求和的例子，其实同样可以轻松地用循环来实现。下面这个函数则是一个更适合用递归来写的例子。

下面的代码针对给定的数字计算斐波那契数列（Fibonacci Sequence）。斐波那契数列是这样一个数列：1, 1, 2, 3, 5, 8, 13, 21, 34, …… 数列中的每个数都等于它前面两个数之和。基本情况是 Fibonacci(0) = 1 以及 Fibonacci(1) = 1 。

Java
Java (Generic)
C++

long Fibonacci(int n) {
  if (n < 2) {
    return 1;   
  }
  return Fibonacci(n - 1) + Fibonacci(n - 2);
} 

long Fibonacci(int n) {
  if (n < 2) {
    return 1;   
  }
  return Fibonacci(n - 1) + Fibonacci(n - 2);
} 

long Fibonacci(int n) {
  if (n < 2) {
    return 1;   
  }
  return Fibonacci(n - 1) + Fibonacci(n - 2);
} 

OpenDSA 完整目录

Chapter 8 Recursion

2. 编写递归函数¶

2.1. 编写递归函数¶