求斐波那契数列得前n项

描述：
斐波那契数列的定义如下：

解法1：递归

macro_rules! input_num {
    () => {
            {
             let mut input = String::new();

             std::io::stdin().read_line(&mut input)
             .expect("Falied to read line");

             input.trim().parse().unwrap()
        }
    };
}

//生成 n 阶斐波那契数列
fn fibonacci(n:u32)->u32{
   if n == 0{
       return  0
   }else if n == 1{
       return  1
   }else{
       return  fibonacci(n-1) + fibonacci(n-2);
   }

}
fn main() {
    loop {
        println!("输入n：");

        let  n:u32  = input_num!();

        println!("Fibonacci:");
        let mut i = 0;
        while i < n{
            print!("{}  ",fibonacci(i));
            i = i + 1;
        }
        println!(" ")
    }
}

时间复杂度分析：


参考：https://blog.****.net/beautyofmath/article/details/48184331【强推】
https://blog.****.net/lxf_style/article/details/80458519【强推】

结果：