# 遞精喔
## Recursion with Memoization (遞迴記憶)

在使用遞迴時，有可能會因過大且重複的計算量，導致記憶體溢位及超時。此時，我們可以利用**遞迴記憶**來幫助我們節省記憶體並省下更多時間。

在遞迴記憶中，我們使用一個陣列來儲存每一個解。當我們需要使用到時，就將陣列中的那項叫出來並進行運算。如此一來，就可大幅省下記憶體空間及運行時間。

## Leetcode 70. Climbing Stairs

### 主程式

int main (void)
{
    int n = 0;
	
    scanf("n = %d", &n);
	
    printf("%d", climbStairs(n));
}

## 函式寫法

使用以下三種寫法

### 1. 一般遞迴

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

### Leetcode 結果

超時


### 2. 遞迴記憶

int result[46] = {0};

int climbStairs(int n)
{
    if(n <= 1)
    {
        return 1;
    }
    
    if(result[n] > 0)
    {
        return result[n];
    }
    
    result[n] = climbStairs(n - 1) + climbStairs(n - 2);
    
    return result[n];
}

### Leetcode 結果

執行時間： 0 ms
記憶體用量： 5.7 MB


### 3. 陣列

int climbStairs(int n)
{
    long long int num[46] = {0};
    
    num[1] = 1;
    num[2] = 2;
    
    for(int i = 3; i <= n; i++)
    {
        num[i] = num[i - 1] + num[i - 2];
    }
    
    return num[n];
}

### Leetcode 結果

執行時間： 0 ms
記憶體用量： 5.4 MB