斐波那契序列：在下面的代码中，可以看到函数 fibonacci (int n) 计算了第 n 个斐波那契序列。斐波那契数列是 0, 1, 1, 2, 3, 5, 8, 13, 21，...。如你所见，该序列的第0个数为 0，该序列的第1个数为 1，依此类推。通常，如果 f(n) 表示斐波那契数列的第 n 个数字，则 f(n) = f(n-1) + f(n-2) 。对于此递归关系，f(0) = 0 和 f(1) = 1是终止条件。
1 public int fibonacci(int n) { 2 if (n == 0 || n == 1) { 3 return n; 4 } 5 6 return (fibonacci(n-1) + fibonacci(n-2)); 7 }
时间复杂度：让我们看一下生成的递归树以计算斐波那契数列的第 5 个数。
在此递归树中，每个状态（除 f(0) 和 f(1) 之外）都会生成两个附加状态，并且生成的状态总数为 15。通常，用于计算第 n 个斐波那契数 f (n) 的状态总数大约等于 2^n。注意，每个状态都表示对 fibonacci(n) 的函数调用，该函数除了进行另一个递归调用外不执行任何操作。因此，计算斐波那契数列第 n 个所需的总时间为 O (2^n)。
请注意，这并不总是正确，为了更准确地进行时间复杂度分析，应该使用主定理。该解释的目的是对递归算法的运行时间有一个总体了解。
空间复杂度：递归算法的空间复杂度计算有些棘手。我们需要了解如何在内存中生成堆栈帧以进行递归调用序列。
让我们尝试大致了解何时生成堆栈帧以及它们在内存中保留了多长时间？从方法 "f0" 调用方法 "f1" 时，将创建与该方法 "f1" 相对应的堆栈帧。该堆栈帧将保留在内存中，直到函数 "f1" 的调用未终止。该堆栈帧负责保存函数“f1”的参数，函数 "f1" 中的局部变量以及调用方函数（函数 "f0"）的返回地址。现在，当此函数 "f1" 调用另一个函数 "f2" 时，也会生成与 "f2" 相对应的堆栈帧，并将其保留在内存中，直到对 "f2" 的调用未终止。调用 "f2" 时，其中具有堆栈框架的调用堆栈如下所示：
现在，当返回对函数 "f2" 的调用时，由于不再需要与 "f2" 相对应的堆栈帧，因此将从内存中删除该堆栈帧。函数 "f1" 和函数 "f0" 的堆栈帧也是如此。
使用此类推方法进行递归调用序列时，应遵循的原则是，在任何时间点内存中可能存在的最大堆栈帧数等于递归树的最大深度。在递归树中，当执行与叶节点状态相对应的调用时，其调用序列可以由从递归树中的根节点到该叶节点的路径表示。例如，在用于计算第五斐波那契数的递归树中，当执行最左端和最底端的状态 f(1) 时，导致该状态的调用序列为 f(5) -> f(4) -> f (3) -> f(2) -> f(1)，所有对应的堆栈帧将出现在内存中，并且当 f(1) 返回时，其堆栈帧将从内存（或调用堆栈）中删除。
总而言之，递归算法的空间复杂度与所生成的最大递归树的深度成正比。如果递归算法的每个函数调用都占用 O(m) 空间，并且如果递归树的最大深度为 n，则递归算法的空间复杂度将为 O(n·m)。