C语言3种斐波那契数列

        斐波那契数列（Fibonacci sequence），又称黄金分割数列、兔子数列。指的是这样一个数列：1、1、2、3、5、8、13、21、34、……；简单说就是前两项之和等于后一项，F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。

排列组合：

        有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第 10 级台阶有几种不同的走法?

        这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种登法……

        1，2，3，5，8，13…… 所以，登上十级，有 89 种走法。

兔子繁殖问题：

        有一只兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子，假如兔子都不死，问第n个月的兔子总数为多少？

        这也是一个斐波那契数列：第一个月有1只兔子，第二个月有一只兔子，第三个月有2只兔子，第四个月有3只兔子，第五个月有5只兔子……从第三个月开始，前一个月的兔子数量就是这个月新出生的兔子数量。

...

思路：

        数学公式 f(n) = f(n-1) + f(n-2)

问题：暴力递归时间复杂度过高，其中进行了极其大量、重复的运算。递归n次，时间复杂度O(2^n)。

2·非递归_顺序循环实现

思路：

        前两项之和等于后一项，所以从前往后求。相比于暴力递归，顺序循环的方法避免了重复的运算。