1

再帰関数とは自分を呼び出してループする関数の事でしょうか?

function myChange() {
    setTimeout(myChange, 5000); 
    let iterative = ()=> {
    iterative = setTimeout(myChange , 5000); 
}

______

ありがとうございます。

初心者には難しくてよくわかりませんが、
コールスタックとは下記の情報を見ると、 処理中のデータを一時的にメインメモリーの一部領域に退避させること
と考えてよいのでしょうか?

>>>
スタック [2] 【stack】
コンピューターで処理中のデータを一時的に退避させること。また,そのための記憶領域やデータ構造。後に格納したデータを先に取り出す。 → 後入先出法

コールスタック (Call Stack)は、プログラムに実行中にサブルーチンに関する情報を格納するスタックである。
実行中のサブルーチンとは、呼び出されたが処理を完了していないサブルーチンを意味する。

私のソースは、定義した自分自身をループはしているが、それが起きないので再帰関数と言えないという事でしょうか?
するとコールスタックが起こるか起こらないかはどう判断できるのでしょうか?

10
  • 1
    spitson さんの回答のコメントにある内容ですが、あなたが掲示された例ではmyChange関数の実行途中では、次のmyChange関数は呼び出されませんので、「自分を呼び出す」「繰り返し処理をする」の2点が成立しても、通常再帰関数とは呼びませんね。
    – OOPer
    Commented 2017年4月21日 10:06
  • setTimeout(myChange, 5000); のchangeで自分自身を5秒ごとに呼び出しているので自分自身を読んだループになっていますがmychange関数は自分を読んでループするので再帰関数と言えるのではないのですか? Commented 2017年4月22日 0:16
  • 1
    setTimeoutによるハンドラーの実行はそれを呼んでいる関数内で行われるのではなく、全く別の実行待ちキューに置かれ、元の関数が終了してから実際の呼び出しが行われます。rio.irikami さんの「呼び出したら自身がコールスタックに複数回乗る」の用語を借用させてもらうと、あなたの例の場合、myChange関数が終了し呼び出しのコールスタックが解放された後にtimer処理によりキューからmyChange関数が取り出されて呼び出されることになります。つまり「コールスタックに(重ねて)複数回乗る」ことはないわけです。このような処理・関数は通常再帰関数とは呼びません。
    – OOPer
    Commented 2017年4月22日 0:27
  • >>> setTimeoutによるハンドラーの実行はそれを呼んでいる関数内で行われるのではなく、全く別の実行待ちキューに置かれ、 ‌​元の関数が終了してから実際の呼び出しが行‌​われます 私の例のsetTimeoutはsetTimeoutの仕様上例の関数内のsetTimeoutは関数内では行われずに別の所で実行されるので違うという事でしょうか? つまり再帰関数とはその関数内で実行される関数のことで、その関数外で実行されるものは入らないという事ですか? Commented 2017年4月25日 8:30
  • その通りです。極端な話、再帰呼び出しが使えなかったとされる古いFORTRANでも、JavaScriptのsetTimer()に相当する機構があれば、同じスタイルでの繰り返し処理は可能です。もう少しだけ丁寧に言うと、「再帰関数というのはその関数内(=呼び出されてから最初の呼び出し元に戻る前)で直接または間接的にその関数自身が実行される関数のこと」と言うことになります。「関数外」であっても、間接的に「最初の呼び出し元に戻る前」に呼び出されていれば、再帰呼び出しと言えますし、もっと直接的に参照しているように見えても(あなたのコード例ですね)最初の呼び出し元に戻った後に別の仕組みで呼び出される場合には、再帰呼び出しとは言いません。「再帰呼び出し」「再帰関数」という言葉に絶対的な権威となりうる意味づけがあるのかどうかは知らないのですが、 rio.irikami さんの回答にあるC言語やECMA Scriptの説明も、「昔のFORTRANでは再帰呼び出しができなかった」という場合も、この意味でrecursive(再帰的)という単語を使っています。
    – OOPer
    Commented 2017年4月25日 10:34

3 件の回答 3

5

「再帰関数」という語の定義にもよりますが、たとえばCなんかは言語仕様でも言及されています。

6.5.2.2 Function calls

11. Recursive function calls shall be permitted, both directly and indirectly through any chain of other functions.

(International Organization for Standardization, ISO 9899:1999 Programming languages -- C, page.72)

4.10 Recursion

C functions may be used recursively; that is, a function may call itself either directly or indirectly.

(Brian W. Kernighan and Dennis M. Ritchie, The C Programming Language, Second Edition, Prentice Hall, 1988, ISBN 0-13-110362-8, 0-13-110370-9, page.86)

14.1.21 Runtime Semantics: Evaluation

Note 2  The BindingIdentifier in a FunctionExpression can be referenced from inside the FunctionExpression's FunctionBody to allow the function to call itself recursively.

(Ecma International, ECMA-262 ECMAScript® 2016 Language Specification, Edition 7, page.283)

コメントにあるお話に関連して、Cではboth directly and indirectlyとされていますね。一方、JavaScript(ECMAScript)ではitself以外については言及していません。

しかしながら、いわゆる「相互再帰関数」も再帰関数の一種とみなしてよいのではないでしょうか。いずれも「呼び出したら自身がコールスタックに複数回乗る」ので、通常の関数とは区別できる挙動をすることが根拠です。

参考までに:

Indirect recursion

Most basic examples of recursion, and most of the examples presented here, demonstrate direct recursion, in which a function calls itself. Indirect recursion occurs when a function is called not by itself but by another function that it called (either directly or indirectly).
...
Indirect recursion is also called mutual recursion, which is a more symmetric term, though this is simply a difference of emphasis, not a different notion.

3

質問に内容が追記されましたので、主にその部分について説明を試みたいと思います。

JavaScriptのように関数を定義して、その関数を呼び出すことが出来る言語の動作を考えてみてください。関数定義は一箇所にしかなくても、その関数の呼び出しはプログラム中のいろいろな場所から行うことができます。

function myFunc() {
    //...
}

//...

myFunc();  //(A)

//...

myFunc();  //(B)

myFunc();という関数呼び出しを実行すると、制御はmyFunc()関数の中身に移って、定義された内容が実行されるわけですが、関数の中身の実行が終わった後は、関数呼び出しの続きを実行しなければいけません。従って関数呼び出しの時には最低でも「この関数の中身の実行が終わったらどこに戻ればいいのか」をどこかに覚えておく必要があります。

一般的な意味での再帰呼び出しを許す言語では、このような情報を「スタック」と呼ばれるデータ構造(先入れ後出し(FILO)なんて言い方もあります)に積み上げる形で保存します。

|
+-戻り先は(A)の後ろです->    myFunc()の呼び出し(A)
                     |
                     |
<---------------------    スタックを戻すと共に戻り先が(A)の後ろであることを知る
|
(A)の後ろの実行を続ける
|
+-戻り先は(B)の後ろです->    myFunc()の呼び出し(B)
                     |
                     |
<---------------------    スタックを戻すと共に戻り先が(B)の後ろであることを知る
|
(B)の後ろの実行を続ける
|
:

と言った感じの流れでコールスタックを使うことにより、(A)のmyFunc();呼び出しが済んだら(A)の続きを、(B)のmyFunc();呼び出しが済んだら(B)の続きを実行することが出来るわけです。

関数呼び出しが式の中に埋め込まれている場合には「(x)の後ろ」とはどこなのか、説明が難しくなるので詳細は省略しますが、「式の計算の続きが実行できるところ」を表現する何かがスタックに保存されるのだと思ってください。

spitson さんの紹介されたフィボナッチ数計算を再帰呼び出しで実現した例では、こんな感じで計算が終わるまでに何度もコールスタックが積まれては取り出され、ということが繰り返されます。

|
+--->          最初のfib(n)の呼び出し
    |
    +--->          fib(n)の実行途中でのfib(n-1)の呼び出し
        |
        +--->          fib(n-1)の実行途中でのfib(n-2)の呼び出し
            :
            :
        <----
        |
        +--->         fib(n-1)の実行途中でのfib(n-3)の呼び出し
            :
            :
        <----
        |
    <----
    |
    +--->        fib(n)の実行途中でのfib(n-2)の呼び出し
        :
        :
    <----
    |
<----
|

nが大きな数の時にはとんでもない大きさの図になるので、ずいぶん端折って、細かい実行順序も無視していますが、雰囲気はわかっていただけるでしょうか。

よって、この質問

コールスタックが起こるか起こらないかはどう判断できるのでしょうか?

に対する回答としては、

コールスタックにデータが積まれるのは、実際に関数が呼び出される時

コールスタックからデータが降ろされるのは、その関数の実行が終了した時

つまり、 実際の関数呼び出しが起これば、コールスタックの操作は必ず発生する ということになります。

あなたが示されたコード(細かい間違いがあるので、setTimeout(myChange, 5000);だけに着目しています)では、JavaScriptに「この関数(myChange)を後で実行してくれ」と指示しているだけで、その関数の実際の呼び出しは起こりません。

従ってmyChange()呼び出し用のデータがコールスタックに積まれた状態(つまりその関数の実行が終了していない状態)で、さらに重ねて(複数、つまり2個目以降の)myChange()呼び出し用のデータがコールスタックに積まれることはありません。このような状態は再帰呼び出しとは言わない(従ってそのように定義された関数は再帰関数とは呼ばない)と言うことです。

関数を「後で実行してくれ」と言う意味でパラメータとして渡すのと、その関数が実際に実行されるのとは別物だと言うことをしっかり区別していただければ、ご理解いただけると思います。

-1

はい。
自分自身を呼び出すような関数です

function fib(n) {
    if (n === 0) return 0;
    if (n < 3) return 1;
    return fib(n-2) + fib(n-1);
}

console.log(fib(10));

7
  • その定義だと、関数fgを呼び出して,gfを呼び出す可能性があるような,相互再帰している関数はどうなるのでしょうか?
    – nekketsuuu
    Commented 2017年4月21日 8:32
  • iterative = setTimeout(myChange , 5000); のmychageの部分 頂いた例の return fib(n-2) + fib(n-1);の flb()の部分 を再帰関数と呼び特別な関数があるわけではなく Commented 2017年4月21日 9:01
  • あくまでこのように関数を使う事を再帰関数というのですね。 Commented 2017年4月21日 9:08
  • > 相互再帰している関数はどうなるのでしょうか? 普通の関数で、特別な名前はないかと思われます
    – spitson
    Commented 2017年4月21日 9:25
  • 2
    @spitson 「再帰関数」の定義にもよるとは思いますが、普通は相互的に再帰している関数のことも再帰関数と言うのではないかと私は思います。
    – nekketsuuu
    Commented 2017年4月21日 9:56

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。