# 作業 2 遞精喔
# 1. 一般遞迴

一般遞迴就是暴力解，他會不斷的重複調用函式計算相同的數字，導致記憶體不斷的增加進而使時間爆炸。

輸出結果 : TLE

int climbStairs(int n){
    if (n == 1){
        return 1;
    }
    else if (n == 2){
        return 2;
    }
    return climbStairs(n - 1) + climbStairs(n - 2);
}    


# 2. 記憶遞迴

將計算出會用到的值暫存在陣列裡，這樣後就不需要重複叫出函式來計算，這樣可以大大減少運算的時間。

輸出結果 : AC
執行時間 : 0 ms
記憶體 : 5.7 MB

int mem[50] = {0};

int climbStairs(int n){
    if (n == 1){
        return 1;
    }
    else if (n == 2){
        return 2;
    }
    if (mem[n] != 0){
        return mem[n];
    }
    else{
        mem[n] = climbStairs(n - 1) + climbStairs(n - 2);
        return mem[n];
    }
}


# 3. 迴圈

輸出結果 : AC
執行時間 : 0 ms
記憶體 : 5.7 MB

int climbStairs(int n) 
{
  int a[50] = {0};
  a[1] = 1, a[2] = 2;

  for(int i = 3; i <= 45; i++)
  {
    a[i] = a[i - 1] + a[i - 2];
  }
  
  return a[n];
}


# 結論
速度 : 迴圈 > 記憶遞迴 > 一般遞迴