首页PTA6-2 递归实现斐波那契数列

PTA6-2 递归实现斐波那契数列

时间: 2025-01-14 17:56:39 浏览: 51

### 斐波那契数列的递归实现在编程中，斐波那契数列可以通过递归来实现。下面是一个简单的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`跟踪每一次函数被调用的过程，最后按照指定格式输出结果。

阅读全文