javascriptの関数の再帰呼び出しがわかりません

Question

javascriptを勉強している小学生です

function f(n) {
	if (n<0) {
		throw new Error('0以上の値を指定してください');
	} else if (n == 0) {
		return 1;
	} else {
		return f(n-1) *n;
	}
} document.write(f(5));

疑問が3つあり、まず1つ目はreturn f(n-1) *nのとき、fの引数が5なのでこの処理が実行され、計算結果の120が表示されます。
しかし一つ上の処理のelse if(n == 0)のreturn 1;をreturn 2;などに変えると処理結果が変わるのですが理由がわかりません。n == 0のときの処理なのでfの引数のnが5の時点でこの処理は除外されるんではないんでしょうか？またreturn 1;はただ1という数値を返しているだけなのですか？

2つ目の疑問は階乗？というものについてです。return f(n-1) nは4321*5をしているらしいのですが(n-1)nなら45ではないんでしょうか？何乗というのは^2や^3などと本に書いてあったので...
そして(n-1)*nではなく、なぜf(n-1)*nにしているのですか？
関数内でそんな処理をしていないのに(n-1)*nとf(n-1)*nでは結果が変わってしまいます。

3つ目はreturnというものについてなのです。これは関数の引数に指定したものを使っておこなった処理結果を外に出すというためのものですか？返すというらしいのですがその考えを自分は外にだすというふうに捉えています、勉強していると今回のように引数に指定していないもの return 1;などがあり混乱するのですが、自分の捉え方は間違っているのですか？

文章がうまく書けなくわかりにくいでしょうが教えてくださるとうれしいです。宜しくお願いします

Answer 1

お邪魔します。

小学生なのにすごいですね。私がご飯を食べられなくなる日も近そうです。笑

まず(疑問1)

else if(n == 0)のreturn 1;をreturn 2;などに変えると処理結果が変わるのですが理由がわかりません。n == 0のときの処理なのでfの引数のnが5の時点でこの処理は除外されるんではないんでしょうか？またreturn 1;はただ1という数値を返しているだけなのですか？

returnは呼び出し元に関数を実行した結果を返却する（返す/戻す）命令です。
return 1;はf(n)を呼び出した処理に1を返しているだけです。

fの引数のnが5の時点でこの処理は除外されるんではないんでしょうか？

f(5)の時実行されるのは return f(n-1)*n;です。n=5なのだからf(5-1)*5で、fに5-1、つまり4を渡して呼び出し、その結果と5を掛けます。
f(4)の時もf(4-1)*4が実行されるのでfに4-1つまり3を渡して呼び出し、その結果と4を掛けます。
というのがn==0となるまで1ずつ減って実行されていくので、最終的にはn == 0がtrueとなる呼び出しが実行されて、その時はreturn 1;が実行されるのです。
ちょっとややこしいかも知れないので、これは後で詳しく見ましょう。

(疑問2)

階乗？というものについてです。return f(n-1) nは4321*5をしているらしいのですが(n-1)nなら45ではないんでしょうか？

f(n-1)*nと(n-1)*nは違う命令です。f(n-1)はfunction f(n)にn-1を渡して実行するという命令です。
呼び出した側と呼び出される側に両方nが登場してしまっているのですごくわかりにくいですが、この２つは同じ名前だけれど別のものです。

例えば、
f(5)のとき →　f(n)内部でnは5。n-1は4。f(n-1)はf(4)。
f(4)のとき →　f(n)内部でnは4。n-1は3。f(n-1)はf(3)。
f(3)のとき →　f(n)内部でnは3。n-1は2。f(n-1)はf(2)。
f(2)のとき →　f(n)内部でnは2。n-1は1。f(n-1)はf(1)。
f(1)のとき →　f(n)内部でnは1。n-1は0。f(n-1)はf(0)。
f(0)のとき →　f(n)内部でnは0。n-1は-1。
って感じです。

(疑問3)

3つ目はreturnというものについてなのです。これは関数の引数に指定したものを使っておこなった処理結果を外に出すというためのものですか？

関数を呼び出した処理に、処理した結果を渡す、という命令です。
引数を使うか使わないかはfunctionを作る人の自由ですが、引数は無しにもできるのですから、処理に必要で渡しているのでしょう？
そうであるならほとんどの場合は、引数を使って何かの計算や処理をおこない、その結果をreturnするのですよね。
結果を返さない関数を作ることもありますし(副作用を目的にした関数、といいます。あまりよいやり方ではないですが。)、やりたいことに応じて君がデザインすればよいのですよ。

実際にプログラムを書いていると、引数を使わないで結果をreturnする、ということはたまにあります。
いろんな使い方がありますが、例えば足し算をするプログラムで

function add(a, b) {
	if(a == null || b == null) {
		//aとbのどちらかがnull(またはundefined)の場合は計算不可能なのでnullを返す
		return null;
　　　    
        //aとbのどちらかがnull(またはundefined)の場合は数字の方を返し両方null(またはundefined)の場合は0を返す時はこんな感じ
		//return a　|| b ? a　|| b : 0;
	} else {
	    //両方nullじゃない場合は足し算の結果を返す
		return a + b;
	} document.write(add(null, 1))
}

こんな風に、エラーチェックをする場合などに使います。
（作ったときに予想した引数以外が間違って渡されてしまった場合にもちゃんと動くようにしておくために使います。）

（番外）再帰呼び出しの説明
後に回しておいた分の説明です。
再帰呼び出し、ですね。再帰呼び出しでは同じ関数（＝自分自身）を何回も呼び出します。
少し長くなりますが、実行される処理をステップを追って見ていくとわかりやすいと思います。

(今からやるのは「ステップ実行」の真似事です。
summer_slt_turnさんご自身のPCの環境でも、javascriptをステップ実行することができれば、私が省略した部分も含めて動きを簡単に見ることができるのですが、ソース中にdocument.writeなどの記載が見受けられるのでブラウザで動かしていますか？ブラウザだったらChromeやIEの開発者ツールを使うとか、Firefoxでfirebugを使うとかすると一行ずつどのようにプログラムが実行されるのか確認できて便利だと思いますよ。)

長くなりすぎないように、n=3でやってみますね。

①function fをn=3を渡して呼び出す

    function f(n) {
        if (n<0) {
            throw new Error('0以上の値を指定してください');
        } else if (n == 0) {
            return 1;
        } else {
            return f(n-1) *n;
        }
①→  } document.write(f(3));

②function fがn=3を受け取る

②→  function f(n) {
        if (n<0) {
            throw new Error('0以上の値を指定してください');
        } else if (n == 0) {
            return 1;
        } else {
            return f(n-1) *n;
        }
   } document.write(f(3));

③n=3なので n < 0 はfalse, n == 0 はfalseとなりelseに入る

    function f(n) {
        if (n<0) {
            throw new Error('0以上の値を指定してください');
        } else if (n == 0) {
            return 1;
③→      } else {
            return f(n-1) *n;
        }
   } document.write(f(3));

④n=3なのでf(3-1) * 3が実行される
※f(3-1)、つまりf(2)の結果はまだ不明なので、3をかける前に先に評価(=先に実行)される

    function f(n) {
        if (n<0) {
            throw new Error('0以上の値を指定してください');
        } else if (n == 0) {
            return 1;
        } else {
④→          return f(n-1) *n;
        }
   } document.write(f(3));

⑤fがn=2を受け取る

⑤→  function f(n) {
        if (n<0) {
            throw new Error('0以上の値を指定してください');
        } else if (n == 0) {
            return 1;
        } else {
            return f(n-1) *n;
        }
   } document.write(f(3));

⑥n=2なのでelseへ。f(2-1)*2が実行される。
※f(2-1)、つまりf(1)の結果はまだ不明なので、2をかける前に先に評価(=先に実行)される

    function f(n) {
        if (n<0) {
            throw new Error('0以上の値を指定してください');
        } else if (n == 0) {
            return 1;
        } else {
⑥→          return f(n-1) *n;
        }
   } document.write(f(3));

⑦fがn=1を受け取る

⑦→  function f(n) {
        if (n<0) {
            throw new Error('0以上の値を指定してください');
        } else if (n == 0) {
            return 1;
        } else {
            return f(n-1) *n;
        }
   } document.write(f(3));

⑧n=1なのでelseへ。f(1-1)*1が実行される。
※f(1-1)、つまりf(0)の結果はまだ不明なので、1をかける前に先に評価(=先に実行)される

    function f(n) {
        if (n<0) {
            throw new Error('0以上の値を指定してください');
        } else if (n == 0) {
            return 1;
        } else {
⑧→          return f(n-1) *n;
        }
   } document.write(f(3));

⑨fがn=0を受け取る

⑨→  function f(n) {
        if (n<0) {
            throw new Error('0以上の値を指定してください');
        } else if (n == 0) {
            return 1;
        } else {
            return f(n-1) *n;
        }
   } document.write(f(3));

⑩[f(n)の呼び出し時n=0] n=0なのでn==0がtrueとなり、return 1;が実行される。関数fは1を呼び出し元に返して処理を終了する。
※現在のfは⑧で呼び出されたものなので⑧の処理が次へ進む

    function f(n) {
        if (n<0) {
            throw new Error('0以上の値を指定してください');
        } else if (n == 0) {
⑩→          return 1;
        } else {
            return f(n-1) *n;
        }
   } document.write(f(3));

⑪[f(n)の呼び出し時n=1] ⑩でf(0)が1を返したので、f(0)*1 = 1×1 = 1となり、1を呼び出し元に返して処理を終了する
※現在のfは⑥で呼び出されたものなので⑥の処理が次へ進む

    function f(n) {
        if (n<0) {
            throw new Error('0以上の値を指定してください');
        } else if (n == 0) {
            return 1;
        } else {
⑪→          return f(n-1) *n;
        }
   } document.write(f(3));

⑫[f(n)の呼び出し時n=2] ⑪でf(1)が1を返したので、f(1)*2 = 1×2 = 2となり、2を呼び出し元に返して処理を終了する
※現在のfは④で呼び出されたものなので④の処理が次へ進む

    function f(n) {
        if (n<0) {
            throw new Error('0以上の値を指定してください');
        } else if (n == 0) {
            return 1;
        } else {
⑫→          return f(n-1) *n;
        }
   } document.write(f(3));

⑬[f(n)の呼び出し時n=3] ⑫でf(2)が1を返したので、f(2)*3 = 2×3 = 6となり、6を呼び出し元に返して処理を終了する
※現在のfは①で呼び出されたものなので①の処理が次へ進む

    function f(n) {
        if (n<0) {
            throw new Error('0以上の値を指定してください');
        } else if (n == 0) {
            return 1;
        } else {
⑬→          return f(n-1) *n;
        }
   } document.write(f(3));

⑭document.writeにf(3)が返した6が渡される。

    function f(n) {
        if (n<0) {
            throw new Error('0以上の値を指定してください');
        } else if (n == 0) {
            return 1;
        } else {
　　          return f(n-1) *n;
        }
⑭→ } document.write(f(3));

こんな感じになります。
１ステップづつゆっくり追っていくのがよいと思ったので長々と書いてしまいました。
長すぎてごめんなさい。

わからなかったら、どこがわからないかまた教えてくださいね。

Comments

[summer_slt_turn]

返信が遅くなってしまいごめんなさい。
とても詳しく説明していただいたおかげでなんとなく感覚がつかめたような気がします！
再帰呼び出しとは文字通りの意味だったのですね(笑)
関数内で条件にあうまで処理をループさせるという感じで捉えていいのですか？

[ShinpeiYamamoto]

そうですね。計算機科学上の理論では、すべての再帰はループでも実装できることになっています。LispやHaskellなどの関数型言語（javascriptも一応関数型なのですが...）では副作用を嫌うので再帰をよく使います。普段ループで書くものを再帰で書くのも面白いですし、普段再帰で書くものをループにするのも面白いいい勉強になります。

Answer 2

イメージとしては合わせ鏡か何かでしょうか
うまく説明できませんが、処理の流れとしては以下のようになります

f(4) * 5
 └ f(3) * 4
    └ f(2) * 3
       └ f(1) * 2
         └ 1 // (*1)

=> return 5 * 4 * 3 * 2 * 1

n == 0 の条件が満たされない限り、再び自分自身を呼び出します

コードの記述にあるif (n == 0) return 1 が最後の数値返却処理に対応していて、返す値を変更すると、それに応じて(*1) の数値が変化するのです

(if (n == 0) return 1 によって自分自身を呼び出すのをやめ、1 を返すことで、計算式が成立します)

累乗の場合は、階乗と違って引数を2つ必要とし、渡された片方の値を計算回数のカウントのために利用します

function power(m, n) {
  if (n == 0) {
    return 1;
  } else {
    return m * power(m, n - 1);
  }
}
document.write(power(3, 3)); // => 27

return については、下記のように わりかし自由に記述することができます

function hello(name) {
  return 'Hello, John!';
}
document.write(hello('Alice')); // => Hello, John!

Links

• 累乗と階乗の違いを教えてください - 累乗は、同じものを、指数と... - Yahoo!知恵袋
• javascript で検索した結果 - プログラミングならドットインストール
• JavaScript | Codecademy
• teaching - How do I explain "Recursion" to a 8 years old kid? - Programmers Stack Exchange

Comments

[gouf]

for やwhile で書いた場合には、結果保持変数を必要とし、計算と代入が逐次行われますが、再帰の場合は実際の計算が最後に実行される点が特徴のひとつなのかもしれません

[gouf]

return は確かに「外に出す」という考えで合っているとは思います
今回の再帰の場合はその外に出すがどんどん包まれていくイメージですね

Answer 3

再帰呼び出しというものがよくわからないと言うことですよね。
人が5人並んでいるとします。一番左の人に「何歳ですか？」と聞くと「右の人と同じです」。その右の人に聞くとまた「右の人と同じです」。最後に一番右の人に聞くと「20歳です」。
これを関数で書くと、一番左の人を5番、一番右の人を1番として、

function age(n){ //引数が自然数以外ならエラーにするチェックは省略
  if(n==1) {
    return 20;
  } else {
    return age(n-1);
  }
}
alert(age(5)); //==> 20と表示

一番右の人の答えが変わると全員の年齢が変わってしまいます。

階乗の場合は、計算が入りますが、5番目の人に「あなたの番号の階乗はいくつですか？」ときくと、「右の人の答えに5を掛けたものです」。となりの4番目の人に聞くと、「右の人の答えに4を掛けたものです」。最後の1番目の人に聞くと「1です」。

これで１つ目と２つ目の質問の答えになりますでしょうか？

3つ目は、質問文からはあなたがどこまでわかっているのかが、わかりにくいので、答えになっているかどうか。
関数というのは、何らかの入力（引数）を与えると、何かの結果を返してくれる物です。
「SUICA」と「ボタン押し」という入力を与えると「ペットボトル」が出てくる自販機のようなもの。
この場合は、関数内でreturn ペットボトル;が実行されているわけです。
他の形での出力を副作用と言います。「ありがとうございます」と言ったり、SUICAの残高を更新したり、光を出したり、電力を消費したりなどが副作用です。
関数によっては、副作用を行うことが主目的となり、結果を返さない物もあり、そういうものではreturnが無かったり、返値無しのreturn;だったりします。

JavaScriptの関数の副作用の例としては、ダイアログをだしたり、HTMLを書き換えたり、サーバーと通信したり、グローバル変数等の外のスコープの変数を更新したり等があります。他の言語だと、ファイルを読んだり、ファイルに書いたり、DBを更新したり等も。

「副作用が主目的」って、日本語としておかしいじゃないかと思いますが、関数が返値以外で関数外に及ぼす影響のことを「副作用」と言うことになっているので、言葉にはあまりこだわらないでください。