PTA7-1-4 斐波那契数列的询问

### 斐波那契数列的递归实现 在编程中，斐波那契数列可以通过递归来实现。下面是一个简单的Java程序来展示如何通过递归计算斐波那契数列的第n项[^3]。 ```java public class Solution { public int Fibonacci(int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } return Fibonacci(n - 1) + Fibonacci(n - 2); } } ``` 这段代码定义了一个名为`Solution`的类，在其中有一个公共的方法`Fibonacci`接受一个整型参数`n`并返回该位置上的斐波那契数值。当`n`等于0时返回0；当`n`等于1时返回1；对于其他情况，则是前两项之和的结果。 另外，为了满足特定平台的要求，比如PTA6-2可能需要不同的输入输出处理以及更详细的调试信息。这里提供一段Python版本的例子，它不仅实现了基本功能还增加了计数器用于统计每次调用的情况[^5]： ```python def fibonacci_with_count(n, memo={}): global call_count call_count += 1 if n in memo: return memo[n], call_count elif n <= 1: result = n else: result, _ = fibonacci_with_count(n-1) temp, __ = fibonacci_with_count(n-2) result += temp memo[n] = result return result, call_count if __name__ == "__main__": call_count = 0 n = int(input("Input n: ")) for i in range(1, n+1): fib_i, count = fibonacci_with_count(i) print(f"Fib({i})={fib_i}, count={count}") ``` 此段Python代码同样遵循了斐波那契序列的基本逻辑，并引入了一个字典`memo`来进行记忆化存储以减少重复计算提高效率。同时利用全局变量`call_count`跟踪每一次函数被调用的过程，最后按照指定格式输出结果。

斐波那契数列是一个经典的递归问题，其特点是每个数字（从第三项开始）都是前两项的和。通常，我们可以使用递归来计算第n个斐波那契数。以下是使用递归方法求解的Python示例： ```python def fibonacci_recursive(n): if n <= 0: return "输入值错误，斐波那契数列索引应为正整数" elif n == 1 or n == 2: return 1 else: return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2) # 测试 print(fibonacci_recursive(7)) # 输出：13 ``` 在这个函数中，当n等于1或2时，直接返回1（因为它们分别是斐波那契数列的第一和第二项）。对于大于2的n，函数会递归地调用自身两次，将前两个数相加得到结果。 然而，递归解决大数值的斐波那契数会有性能问题，因为它会重复计算很多次相同的子问题。为了优化，可以使用记忆化搜索（如动态规划）来存储已经计算过的值。