# 遞精喔
**D1149682 林允勝**
### 一般迴圈

int climbStairs(int n) {
    int step1, step2;
    
    if (n == 0 || n == 1 || n == 2) {
        return n;
    }
    
    step1 = 1;
    step2 = 2;
    
    for (int i = 3; i <= n; i++) {
        step2 = step1 + step2;
        step1 = step2 - step1;
    }
    return step2;
    //1,2,3,5,8,13,21==Fibonacci
}

**Runtime 0ms Memory 5.5mb**
### 遞迴

#include <stdio.h>

int climbStairs(int n){
  if (n==1) return 1;
  if( n==2) return 2;

  while(n>=3){
      return climbStairs(n-2)+climbStairs(n-1);
  }
  if(n<=0){
    return 0;
  }
}

### TLE
### memorization recursion

int memo[46] = {0};

int climbStairs(int n){
    
    if (n == 1 || n == 0)
        return 1;
    
    if (memo[n] != 0)//
        return memo[n];//如果已在 memo array 中存在,則直接return。
    
    return memo[n] = climbStairs(n-1) + climbStairs(n-2);
}

**0ms 5.5MB**

## 由以上可以推論節省記憶體與速度的方面:
### 一般的迴圈≈memorization recursion>>遞迴
## conclusion
### 因為遞迴需要不斷重新計算array中的同一個element ，memorization中則是將結果記載在一個array裡，如果有答案便直接回傳，而一般迴圈則只用前兩項相加易於釋放記憶體。