Help us understand the problem. What is going on with this article?

# 階乗

## 再帰を使わない解法

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

### 計算時間計測

```%%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
```

## 再帰関数

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

### 計算時間計測

```%%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
```
```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)
```

## 計算時間の比較

```%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)')
```

# フィボナッチ数列

フィボナッチ数列は漸化式 xi = xi - 1 + xi - 2 で表せます。

## 再帰を使わない解法

```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]
```
```fib_while(10)
```
```55
```

### 計算時間計測

```%%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
```

## 再帰関数１

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

### 計算時間計測

```%%timeit
fib_recursive(10)
```
```100000 loops, best of 3: 17.3 µs per loop
```

## 再帰関数２

```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]
```
```fib_recursive2(10)
```
```55
```

### 計算時間計測

```%%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
```

## 計算時間の比較

```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)
```
```%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)')
```

```%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)')
```

# 課題

1. 計算時間は実行ごとに異なることを確認しなさい。
2. 再帰関数と、再帰を使わない解法の違いについて説明しなさい。
3. それぞれの関数で、n や i の値を出力し、どういう順序で計算が行われているか説明しなさい。
4. 上の fib_recursive は、fib_recursive2 に比べて計算効率が悪い。その理由を説明しなさい。
Why not register and get more from Qiita?
1. We will deliver articles that match you
By following users and tags, you can catch up information on technical fields that you are interested in as a whole
2. you can read useful information later efficiently
By "stocking" the articles you like, you can search right away