实验二:递归与递推

算法设计与分析

实验二:递归与递推

1. 实验目的

以斐波那契数列为例,掌握递归与递推算法。

2. 实验内容

斐波那契数列

请用三种方式写出求斐波那契数列第n项,包括普通递归,带缓存数组的递归以及递推法。斐波那契数列的公式如下:

f(n)={1if n=1,2f(n−1)+f(n−2)if n>2f(n) = \begin{cases} 1 & \text{if } n=1,2 \\ f(n-1)+f(n-2) & \text{if } n>2 \end{cases}

输入样例
第一行n,表示求斐波那契数列的第n项

5

输出样例
包含一个数字,为斐波那契数列的第n项。

5

算法分析

针对斐波那契数列的算法,请进行以下分析:

  1. 选取不同的n,用表格的形式测试对于不同的n,算法的运行时间。(注意n的选取)
  2. 分析算法间效率的差距
  3. 对于不带缓存数组的递归形式,请画出n=5时的递归树

3. 实验要求

请写出题目的思路、代码,并完成算法分析。

提示: