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

階乗

階乗は漸化式 x_i = n * x_{i - 1} で表せます。

再帰を使わない解法

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

フィボナッチ数列

フィボナッチ数列は漸化式 x_i = x_{i - 1} + x_{i - 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 に比べて計算効率が悪い。その理由を説明しなさい。