質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.51%

  • Ruby

    7707questions

    Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

  • アルゴリズム

    414questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

  • 再帰

    29questions

    情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

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

解決済

回答 6

投稿

  • 評価
  • クリップ 3
  • VIEW 887

OOO_777

score 40

該当のソースコード

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

理解できていない点

この場合、5*4*3*2*1となると思いますが、
どうしても理解できません。

5*4, 4*3, 3*2, 2*1, 1*0
このようなイメージにしかなりません。

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 6

+4

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 18:31

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

    キャンセル

+2

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

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

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/10/15 18:32

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

    キャンセル

+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) }


実行結果
イメージ説明

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/10/15 21:08

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

    キャンセル

checkベストアンサー

+1

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/10/15 18:33

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

    キャンセル

+1

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)の結果が1*1=1で確定します。
これが待たせた順と逆順に遡っていき、
factorial(2)=2*1=2
factorial(3)=3*2=6
factorial(4)=4*6=24
factorial(5)=5*24=120
と、順次確定していきます。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/10/15 18:34

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

    キャンセル

+1

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/10/15 18:34

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.51%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 解決済

    見栄え無視!とにかく軽くしたい

    rubyです。 0以上且つ9桁以下の整数値データを渡すと、加工して返す関数を作成しました。 行っている処理は ①送り値の数値を一桁ずつ調べていき、  1.その桁の数値が

  • 解決済

    押されているキーの取得

    いつもお世話になっております。 クイズを作っているのですが、答えあわせをするときに使っている人がどのキーを押したのか知りたいので以下のようなソースを作りましたが、うまく実行されま

  • 解決済

    RubyでのFor文

    RubyのFor文で範囲オブジェクトを-1から始めようとするとsyntax error, unexpected tUMINUS_NUMとエラーが出ます 全文がこんな感じなので

  • 解決済

    Rubyでの型変換

    C++の bool(*decision[])(int) = { decision, decision2 }; をRubyで書きたくて調べたのですが、うまく書けません

  • 解決済

    raiseで出力したメッセージをminitestでテストしたい

    下記のrubyプログラムのif文の中を、aが2以上ならばraiseで"エラー"を、そうでなければ変数msgに"エラーではない"という文字列を代入して、minitestのassert

  • 受付中

    コマンドプロンプトで計算ゲームをしたいが、正解率の所でエラーになる件

    ご覧いただきありがとうございます。 現在、コマンドプロンプト(ターミナル)で計算ゲームをするプログラムを作っています(おもに練習用です) まだrubyの勉強初めて一週間

  • 受付中

    ruby とある問題での回答例。関数やクラス使えそうか?

    失礼します。 とある問題を説いていたら次のようなコードになりました。(問題の内容は拡散禁止されているため個人的な回答内容から読み取ってください。) ちなみに入力される値はこ

  • 解決済

    RubyでFizzbuzz問題

    前提・実現したいこと 初めて投稿するので、不備等があり失礼な質問をしてしまうかもしれませんがよろしくお願いします。 Rubyで下記の設定でFizzBuzz問題を解決したいです。

同じタグがついた質問を見る

  • Ruby

    7707questions

    Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

  • アルゴリズム

    414questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

  • 再帰

    29questions

    情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。