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

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

階乗

階乗は漸化式 xi = n * xi - 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)')

output_12_1.png

フィボナッチ数列

フィボナッチ数列は漸化式 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

再帰関数1

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

再帰関数2

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

output_30_1.png

%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

課題

  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
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  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