

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

例

[code]

    function myChange() {
        setTimeout(myChange, 5000); 
        let iterative = ()=> {
        iterative = setTimeout(myChange , 5000); 
    }
    
[/code]

＿＿＿＿＿＿

ありがとうございます。

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

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

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

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


CC BY-SA 3.0
2017-04-21T06:45:19.917
34181
2017-04-22T04:58:59.920
2017-04-22T01:38:18.807
20834
20834
question
javascript
再帰関数とは自分を呼び出してループする関数の事でしょうか？


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

[code]

    function fib(n) {
        if (n === 0) return 0;
        if (n < 3) return 1;
        return fib(n-2) + fib(n-1);
    }
    
    console.log(fib(10));
[/code]


CC BY-SA 3.0
2017-04-21T06:59:21.173
34182
2017-04-21T06:59:21.173
15705
34181
answer


「再帰関数」という語の定義にもよりますが、たとえば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_](https://www.iso.org/standard/29237.html), 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](http://freecomputerbooks.com/The-C-Programming-Language.html),
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](https://www.ecma-
international.org/publications/standards/Ecma-262.htm), page.283)

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

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

参考までに:

> ### [Indirect
> recursion](https://en.wikipedia.org/wiki/Recursion_\(computer_science\)#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](https://en.wikipedia.org/wiki/Mutual_recursion)** , which is a
> more symmetric term, though this is simply a difference of emphasis, not a
> different notion.


CC BY-SA 3.0
2017-04-21T09:46:51.213
34189
2017-04-21T10:07:16.860
2017-04-21T10:07:16.860
34181
answer


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

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

[code]

    function myFunc() {
        //...
    }
    
    //...
    
    myFunc();  //(A)
    
    //...
    
    myFunc();  //(B)
    
[/code]

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

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

[code]

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

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

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

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

[code]

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

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

よって、この質問

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

に対する回答としては、

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

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

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

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

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

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


CC BY-SA 3.0
2017-04-22T04:58:59.920
34201
2017-04-22T04:58:59.920
13972
34181
answer