【再帰関数】階乗を求める再帰関数：数値の動きが理解できない

Question

###該当のソースコード

def factorial(n)
  return 1 if n == 0
  return n * factorial(n - 1)
end
p factorial(5) #=> 120

###理解できていない点

この場合、54321となると思いますが、
どうしても理解できません。

54, 43, 32, 21, 1*0
このようなイメージにしかなりません。

この再帰関数の数値の動きを教えて頂きたいです。

Answer 1

factorial(n)をn*factorial(n-1)で置き換えると...

factorial(5)
-> 5 * factorial(4)
-> 5 * 4 * factorial(3)
-> 5 * 4 * 3 * factorial(2)
-> 5 * 4 * 3 * 2 * factorial(1)
-> 5 * 4 * 3 * 2 * 1 * factorial(0)
factorial(0)は1を返す(置き換えはこれでオシマイ)から
-> 5 * 4 * 3 * 2 * 1 * 1

Comments

[OOO_777]

ご回答ありがとうございます。
そのような動きになるのですね。
勉強になります。ありがとうございます。

Answer 2

factorial メソッドを計算結果だけでなく、計算式も返すようにしてみました。

factorial.rb

def factorial_1(n)
  return [1, '0!'] if n == 0
  n_prev, exp_prev = factorial_1(n - 1)
  return [n * n_prev, "#{n} * #{n-1}!"]
end

def factorial_2(n)
  return [1, '1'] if n == 0
  n_prev, exp_prev = factorial_2(n - 1)
  return [n * n_prev, "#{n} * #{exp_prev}"]
end

(0..5).each { |n| p factorial_1(n) }
puts
(0..5).each { |n| p factorial_2(n) }

実行結果

Comments

[OOO_777]

ご回答ありがとうございます。
だんだんイメージが掴めてきました。
丁寧な説明ありがとうございます。

Answer 3

5*4, 4*3, 3*2, 2*1, 1*0ではなくて
5*(4*(3*(2*(1*(1)))))となります。

再帰は、「中に埋め込んでいく」感じです。

追記
多分これ見ると分かりやすい。
http://pythontutor.com

Comments

[OOO_777]

ご回答ありがとうございます。
再帰は、「中に埋め込んでいく」感じです。←ありがとうございます。
またリンクもありがとうございます。

Answer 4

参考情報

• 再帰のお勉強 階乗

http://www.pro.or.jp/~fuji/puzzlestudy/recursive/fact.html

• アルゴリズムとデータ構造 214 ページ

https://books.google.co.jp/books?id=LTmFmni0r6QC&pg=PA214&lpg=PA214&dq=%E5%86%8D%E5%B8%B0+%E9%9A%8E%E4%B9%97&source=bl&ots=4SpO3rpuVj&sig=0GDNkIg9vQYIlHr0-ewrNR5s33w&hl=ja&sa=X&ved=0ahUKEwjkvafim_LWAhWDi5QKHbOLAfYQ6AEImgEwEw#v=onepage&q=%E5%86%8D%E5%B8%B0%20%E9%9A%8E%E4%B9%97&f=false

• 今年こそは再帰関数を理解しよう！

http://note.crohaco.net/2017/recursive-function/

Comments

[OOO_777]

ご回答ありがとうございます。
URL参考にさせて頂きます。
ありがとうございます。

Answer 5

factorial(5)の結果として5*factorial(4)を返そうとするのですが、
factorial(4)がわからないのでfactorial(5)の処理を一旦置いといてfactorial(4)を計算します。
するとその計算にfactorial(3)が必要なのでその計算をします。
これを繰り返して、

factorial(5)=5*factorial(4)(待ち)
factorial(4)=4*factorial(3)(待ち)
factorial(3)=3*factorial(2)(待ち)
factorial(2)=2*factorial(1)(待ち)
factorial(1)=1*factorial(0)(待ち)
factorial(0)

という状態になります。
factorial(0)は定義から1なので、ここで待たせていたfactorial(1)の結果が11=1で確定します。
これが待たせた順と逆順に遡っていき、
factorial(2)=21=2
factorial(3)=32=6
factorial(4)=46=24
factorial(5)=5*24=120
と、順次確定していきます。

Comments

[OOO_777]

ご回答ありがとうございます。
イメージが掴みやすいご説明もありがとうございます。
勉強になります。ありがとうございます。

Answer 6

printデバッグを埋め込んでどう動いているのかを確認するのも一つです。各処理をバラバラにしていますが、下は同じ事をしています。実行して確認してみてください。

def factorial(n, deps = 0)
  puts ("=>" * deps) + "[n=#{n}] factorialを#{n}で開始します。"
  if n == 0
    puts ("=>" * deps) + "[n=#{n}] nが0なので、1を返し、終了します。"
    return 1
  end
  puts ("=>" * deps) + "[n=#{n}] #{n - 1}で再帰的に呼び出します。"
  result_pre = factorial(n - 1, deps + 1)
  puts ("=>" * deps) + "[n=#{n}] 再帰の結果は#{result_pre}です。それに#{n}をかけます。"
  result = n * result_pre
  puts ("=>" * deps) + "[n=#{n}] 最終結果は#{result}です。その値で返し、終了します。"
  return result
end
p factorial(5) #=> 120

Comments

[OOO_777]

ご回答ありがとうございます。
コードありがとうございます。
実行してみたところ、何となく理解できてきたと感じます。