斐波那契数列的递归和非递归法两种表示方法能解释一下是为什么呢？

Question

非递归法
unsigned long long Fibonacci(unsigned long long n)
{
int n1, n2, temp, i;
if (n > 2)
for (n1 = 1, n2 = 1, i = 3; i <= n; i++)
{
temp = n1 + n2;
n1 = n2;
n2 = temp;
}
else n2 = 1;

return n2;

}
递归法
unsigned long long Fibonacci(unsigned long long n)
{
if(n > 2)
return Fibonacci(n - 1) + Fibonacci(n - 2);
else
return 1;
}

Answer 1

非递归的话是不断更新两个斐波那契数来实现求n个斐波那契数，递归的话是不断的把一个斐波那契数表示成两个斐波那契数的和的形式，然后找到最低端的斐波那契数，然后不断的回溯。