再帰関数と再帰を使わない解法


# 階乗

階乗は漸化式 x<sub>i</sub> = n * x<sub>i - 1</sub> で表せます。

## 再帰を使わない解法


```python
def fact_while(n):
    ans = 1
    i = 1
    while i < n:
        i += 1
        ans *= i
    return ans
```


```python
fact_while(10)
```




    3628800



### 計算時間計測


```python
%%timeit 
fact_while(10)
```

    The slowest run took 5.53 times longer than the fastest. This could mean that an intermediate result is being cached.
    1000000 loops, best of 3: 725 ns per loop


## 再帰関数


```python
def fact_recursive(n):
  if n == 0:
    return 1
  else:
    return n * fact_recursive(n - 1)
```


```python
fact_recursive(10)
```




    3628800



### 計算時間計測


```python
%%timeit 
fact_recursive(10)
```

    The slowest run took 4.62 times longer than the fastest. This could mean that an intermediate result is being cached.
    1000000 loops, best of 3: 1.22 µs per loop



```python
import time

X = [10, 20, 40, 60, 80, 100, 120, 140, 160]
Y1 = []
Y2 = []

for x in X:
    start = time.time()
    fact_while(x)
    Y1.append(time.time() - start)
    start = time.time()
    fact_recursive(x)
    Y2.append(time.time() - start)
```

## 計算時間の比較


```python
%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(X, Y1, label="fact_while")
plt.plot(X, Y2, label="fact_recursive")
plt.grid()
plt.legend()
plt.xlabel("X")
plt.ylabel("Time (sec)")
```




    Text(0, 0.5, 'Time (sec)')




![output_12_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211162/42c87a87-7254-ed55-1c3c-ecf865e46fd6.png)




# フィボナッチ数列

フィボナッチ数列は漸化式 x<sub>i</sub> = x<sub>i - 1</sub> + x<sub>i - 2</sub> で表せます。

## 再帰を使わない解法


```python
def fib_while(n):
    list_ = []
    i = 0
    while i < n:
        if len(list_) < 2:
            list_.append(i)
        if len(list_) >= 2:
            list_.append(list_[0] + list_[1])
            list_.pop(0)
        
        i += 1
    return list_[1]
```


```python
fib_while(10)
```




    55



### 計算時間計測


```python
%%timeit 
fib_while(10)
```

    The slowest run took 6.25 times longer than the fastest. This could mean that an intermediate result is being cached.
    100000 loops, best of 3: 3.44 µs per loop


## 再帰関数１


```python
def fib_recursive(n):
  if n <= 1:
    return n
  else:
    return fib_recursive(n - 1) + fib_recursive(n - 2)
```


```python
fib_recursive(10)
```




    55



### 計算時間計測


```python
%%timeit 
fib_recursive(10)
```

    100000 loops, best of 3: 17.3 µs per loop


## 再帰関数２


```python
memo = {}
def fib_recursive2(n):
  if n <= 1:
    return n
  if n in memo:
    return memo[n]
  else:
    memo[n] = fib_recursive2(n - 1) + fib_recursive2(n - 2)
    return memo[n]
```


```python
fib_recursive2(10)
```




    55



### 計算時間計測


```python
%%timeit 
fib_recursive2(10)
```

    The slowest run took 30.53 times longer than the fastest. This could mean that an intermediate result is being cached.
    10000000 loops, best of 3: 133 ns per loop


## 計算時間の比較


```python
import time

X = [5, 10, 15, 20, 25, 30]
Y1 = []
Y2 = []
Y3 = []

for x in X:
    start = time.time()
    fib_while(x)
    Y1.append(time.time() - start)
    start = time.time()
    fib_recursive(x)
    Y2.append(time.time() - start)
    start = time.time()
    fib_recursive2(x)
    Y3.append(time.time() - start)
```


```python
%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(X, Y1, label="fib_while")
plt.plot(X, Y2, label="fib_recursive")
plt.plot(X, Y3, label="fib_recursive2")
plt.grid()
plt.legend()
plt.xlabel("X")
plt.ylabel("Time (sec)")
```




    Text(0, 0.5, 'Time (sec)')




![output_30_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211162/8d292f97-b979-e177-aca4-bc8f31709d69.png)



```python
%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(X, Y1, label="fib_while")
plt.plot(X, Y2, label="fib_recursive")
plt.plot(X, Y3, label="fib_recursive2")
plt.grid()
plt.legend()
plt.yscale("log")
plt.xlabel("X")
plt.ylabel("Time (sec)")
```




    Text(0, 0.5, 'Time (sec)')




![output_31_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211162/0f52a92b-e674-d94e-f99a-e451d693ef5e.png)



# 課題

1. 計算時間は実行ごとに異なることを確認しなさい。
2. 再帰関数と、再帰を使わない解法の違いについて説明しなさい。
2. それぞれの関数で、n や i の値を出力し、どういう順序で計算が行われているか説明しなさい。
3. 上の fib_recursive は、fib_recursive2 に比べて計算効率が悪い。その理由を説明しなさい。