###該当のソースコード
ruby
1def factorial(n) 2 return 1 if n == 0 3 return n * factorial(n - 1) 4end 5p factorial(5) #=> 120
###理解できていない点
この場合、54321となると思いますが、
どうしても理解できません。
54, 43, 32, 21, 1*0
このようなイメージにしかなりません。
この再帰関数の数値の動きを教えて頂きたいです。
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
回答6件
0
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
投稿2017/10/15 03:23
総合スコア16614
0
factorial メソッドを計算結果だけでなく、計算式も返すようにしてみました。
factorial.rb
ruby
1def factorial_1(n) 2 return [1, '0!'] if n == 0 3 n_prev, exp_prev = factorial_1(n - 1) 4 return [n * n_prev, "#{n} * #{n-1}!"] 5end 6 7def factorial_2(n) 8 return [1, '1'] if n == 0 9 n_prev, exp_prev = factorial_2(n - 1) 10 return [n * n_prev, "#{n} * #{exp_prev}"] 11end 12 13(0..5).each { |n| p factorial_1(n) } 14puts 15(0..5).each { |n| p factorial_2(n) }
投稿2017/10/15 10:46
総合スコア22324
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
5*4, 4*3, 3*2, 2*1, 1*0
ではなくて
5*(4*(3*(2*(1*(1)))))
となります。
再帰は、「中に埋め込んでいく」感じです。
追記
多分これ見ると分かりやすい。
http://pythontutor.com
投稿2017/10/15 03:26
編集2017/10/15 05:43退会済みユーザー
総合スコア0
0
参考情報
- 再帰のお勉強 階乗
http://www.pro.or.jp/~fuji/puzzlestudy/recursive/fact.html
- アルゴリズムとデータ構造 214 ページ
- 今年こそは再帰関数を理解しよう!
投稿2017/10/15 08:52
総合スコア22324
0
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
と、順次確定していきます。
投稿2017/10/15 05:17
編集2017/10/15 05:20総合スコア20651
0
ベストアンサー
printデバッグを埋め込んでどう動いているのかを確認するのも一つです。各処理をバラバラにしていますが、下は同じ事をしています。実行して確認してみてください。
Ruby
1def factorial(n, deps = 0) 2 puts ("=>" * deps) + "[n=#{n}] factorialを#{n}で開始します。" 3 if n == 0 4 puts ("=>" * deps) + "[n=#{n}] nが0なので、1を返し、終了します。" 5 return 1 6 end 7 puts ("=>" * deps) + "[n=#{n}] #{n - 1}で再帰的に呼び出します。" 8 result_pre = factorial(n - 1, deps + 1) 9 puts ("=>" * deps) + "[n=#{n}] 再帰の結果は#{result_pre}です。それに#{n}をかけます。" 10 result = n * result_pre 11 puts ("=>" * deps) + "[n=#{n}] 最終結果は#{result}です。その値で返し、終了します。" 12 return result 13end 14p factorial(5) #=> 120
投稿2017/10/15 04:01
編集2017/10/15 04:02総合スコア21735
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2017/10/15 09:31