我想知道为什么这个斐波那契递归函数有效：
int fibRec(int n)
{
if ((n == 1) || (n == 0))
{
return n;
}
int i = fibRec(n - 1) + fibRec(n - 2);
return i;
}
我了解斐波那契数列是什么，也了解递归函数的作用以及该函数的工作原理。我只是很难理解它为什么有效。我知道，当你将其分解时，你本质上是添加了一堆 0 和 1，如下图所示。
但为什么当我将 5 传递给函数并将所有 0 和 1 添加后，它会等于斐波那契数列中的第 5 个数呢？我以前见过这个问题，但从未真正解释过。答案都只是“因为递归”。是的，我知道什么是递归函数以及它是如何工作的。但是为什么这个递归函数会给出正确的斐波那契数列呢？
以下问答涵盖了在 Swift 中生成斐波那契数的一些方法，但它已经过时了（Swift 1.2？）：
问题：我们如何使用现代 Swift (Swift >= 3) 巧妙地生成斐波那契数列？最好是避免显式递归的方法。
我正在尝试在 Scala 中使用记忆功能实现斐波那契函数
这里给出的一个例子使用了一个 case 语句： 在 Scala 中是否有一种通用的记忆方法？
import scalaz.Memo
lazy val fib: Int => BigInt = Memo.mutableHashMapMemo {
case 0 => 0
case 1 => 1
case n => fib(n-2) + fib(n-1)
}
似乎该变量n被隐式定义为第一个参数，但是如果我替换n为_
此外，lazy关键字在这里有什么优势，因为该函数在使用和不使用此关键字的情况下似乎同样有效。
但是，我想将其概括为具有适当类型的更通用的函数定义
import scalaz.Memo
def fibonachi(n: Int) : Int = Memo.mutableHashMapMemo[Int, Int] {
var value : Int = 0
if( n <= 1 ) { value = n; }
else { value = fibonachi(n-1) + fibonachi(n-2) } …我尝试编写一个函数来计算 R 中的第 n 个斐波那契数。我可以递归地执行此操作。
fibonacci = function(n){
if (n == 1) {return(1)}
if (n == 2) {return(2)}
return(fibonacci(n - 1) + fibonacci(n - 2))
}
我在 R 中找不到任何示例，但是从其他语言的指南中我想出了以下内容。然而，它似乎并没有运行得更快。
fibonacci = function(n, lookup = NULL){
if (is.null(lookup)) {
lookup = integer(n + 1)
}
if (n == 1) {return(1)}
if (n == 2) {return(2)}
lookup[1] = 1
lookup[2] = 2
if (lookup[n - 1] == 0) {
lookup[n - 1] = fibonacci(n - 1, lookup)
}
if (lookup[n - 2] …我正在尝试实现一个迭代算法来计算第 N 个斐波那契数的最后 5 位数字。我可以找到第 n 个斐波那契数本身并仅显示最后 5 位数字，但是，我的作业还要求找到我的程序运行时间不到 1 分钟的最大 n。问题是，N 变得非常大，因此斐波那契数也非常大。我应该只使用 BigInteger 来存储值，最后使用 % 运算符来显示最后 5 位数字吗？有没有办法利用我只需要最后 5 位数字来加快流程的事实？我觉得我错过了任务的重点。
作业是这样说的：使用 Java，实现迭代算法来计算第 n 个斐波那契数的最后 5 位数字。进行实验以找出程序在计算机上运行时间不到 1 分钟的最大 n 值。
我用于查找第 N 个斐波那契数的最后 5 位数字的代码：
public static int Fibonacci(int n){
int a, b = 0, c = 1;
for(int i = 1; i < n; i++){
a = b;
b = c;
c = a + b;
}
return c % 100000;
}
我也很想知道是否有更好的迭代解决方案。
只是尝试执行 Hal Daumé III 的 YAHT 手册的练习 3.7（第 31 页），我尝试定义斐波那契函数：
fibo 1 = 1
fibo 2 = 1
fibo n = fibo(n-1) + fibo(n-2)
然后我要求
fibo(3)
并得到：
*** Exception: stack overflow
当我查看练习的解决方案时，我发现了完全相同的代码（不同之处在于该函数被称为 fib 而不是 fibo）。我究竟做错了什么？
（手册是 2006 年的，可能中间语言变了？）（讽刺的是我问 stackoverflow 一个堆栈溢出的问题……）
我正在用 C# 计算斐波那契数，但自从数字 94 以来我得到了错误的数字。
这是我的代码。
static void Main(string[] args)
{
string N = Console.ReadLine();
ulong n = ulong.Parse(N);
ulong[] fibonacci = new ulong[n+1];
fibonacci[0] = 0;
if (n == 1)
{
fibonacci[1] = 1;
}
if (n>=2)
{
fibonacci[1] = 1;
for (ulong i = 2; i < n+1; i++)
{
fibonacci[i] = (ulong)fibonacci[i-1] + (ulong)fibonacci[i-2];
}
}
}
Console.WriteLine(fibonacci[n]);
我一直到第 93 个号码 12200160415121876738 为止，但我在第 94 个号码时得到 1293530146158671551，真正的号码是 19740274219868223167。
我不知道我的代码有什么问题。
我有这个代码以相反的顺序生成斐波那契数列的列表。
fib2(0, [0]).
fib2(1, [1,0]).
fib2(N, [R,X,Y|Zs]) :-
N > 1,
N1 is N - 1,
fib2(N1, [X,Y|Zs]),
R is X + Y.
我只需要第一个元素。问题是这段代码false.在列表之后也给出了一个，所以我尝试获取第一个元素的所有尝试都失败了。有什么方法可以获取列表中的第一个元素，或者使用累加器计算第 N 个斐波那契数的任何其他方法。
提前致谢。
我无法理解尾递归的概念，我想为类似斐波那契的函数制作一个尾递归版本， p1= n-3 ， p2= n-2 ， fx( p1 ) + fx( p2 ) 到目前为止是我想出的，但我不知道这是否是正确的方法，有人可以帮助我，任何帮助将不胜感激 p1= n-3 , p2= n-2 Long doCalc( long n ) { return n = = 0 ? 0 : ( n == 1 ? 1 : ( n == 2 ? 1 : (make( p1 ) + make( p2 )) ) ); }
代码输出正确的结果
但是当我实现尾递归时，我的方法是分裂和征服，但它不起作用并且输出是错误的
Long factor3(Long n, Long a)
{
if( n == 0){
return 0l;
} else if( n == 1 || n …欧拉计划 #2 偶数斐波那契数
斐波那契数列中的每一项新项都是通过添加前两项而生成的。从 1 和 2 开始，前 10 项将是：
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 通过考虑斐波那契数列中值不超过四百万的项，求偶数项的总和。
问题：是否可以在常数时间内解决这个问题？