关于用递归来计算斐波那契数组的问题

Question

正常的方式我懂，不过老师让我们做一个更有效率的递归函数就不是很懂了，大概就是把之前计算出来的值储存起来，这样就不会再去运算计算过的值了。
下面是老师要求的原话：
1. Calculating Fibonacci Numbers
In mathematical terms, the sequence of Fibonacci numbers is defined by the recur-
rence relation Fn=Fn−1+Fn−2,where F0= 0 andF1= 1 .

First think about how to recursively determine the values of specific Fibonacci
numbers. You are required to construct a class called Fibonacci that reads in anumber n and outputs the n-th Fibonacci numberFn.

2.More Efficient Fibonacci Calculation

In order to calculate Fn, you need to recursively calculate Fn−1 and Fn-2. Then, to aclculateF n−1, we needFn−2(again!) andFn−3. This means that many Fibonaccinumbers may be calculated multiple times.Reproduce yourFibonacciclass in another class called EfficientFibonacci.
Make this class efficient by storing calculated numbers. The recursive function should not be called for a number that has already been calculated.

Answer 1

#include <stdio.h>

int arr[1000];
int top = 0;

int Fibonacci(int n)
{
if (n <= 2 && top == 0)
{
top = 2;
arr[0] = 1;
arr[1] = 1;
return arr[n - 1];
}
if (top == n - 1)
{
top = n;
arr[n - 1] = arr[n - 2] + arr[n - 3];
return arr[n - 1];
}
else if (top > n - 1)
{
return arr[n - 1];
}
return Fibonacci(n - 2) + Fibonacci(n - 3);
}

int main()
{
    for (int i = 1; i <= 20; i++)
        printf("%d ", Fibonacci(i));
   return 0;
}