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

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

ただいまの
回答率

87.80%

returnの仕組み

解決済

回答 6

投稿

  • 評価
  • クリップ 0
  • VIEW 9,782

score 258

再呼のコードで、値が見つかればtrueをreturnする、startがendの値を上回ればfalseをreturnしています。
いままであまり考えずにreturnを使っていたのですが、returnを一度すると、ループから抜けてしまうという事ですよね。
returnの仕組みに触れて解説してもらえると嬉しいです。
よろしくお願いします!

コード
bool retrieveItem(int array[], int start, int end, int key){
    if (array[start] == key ){
        return true;
    }
    if (start > end ){
        return false;
    }

    return retrieveItem(array, start+1, end, key);
}
  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 6

+8

再帰呼び出しに限らず関数を呼び出すということは、その関数がマップされているメモリ上のアドレスにジャンプします。
書き方としてretrieveItem関数を呼び出しているように見えますが、内部的にはgoto retrieveItemをしているイメージです。
このときにgotoと違うところはスタックと呼ばれるメモリ空間にgotoをしたところのアドレス(=関数を呼び出したところのアドレス)を記憶しておきます。
returnをするとスタックを参照してそのアドレスへ戻ることができるのです。

関数を呼び出すネストが深くなるとスタックに戻り先のアドレスを積み上げていきます。
この積上げにより戻り先のアドレスがどんどん記憶され、その呼び出した順番を逆に辿って最終的にmain()まで戻ることができるのです。
再帰呼び出しについても自分自身を何回も呼び出すことでスタックを積み上げていき、その積み上がった数だけreturnで戻ることができるのです。

ちなみに関数から戻ったときにスタックに積上げられたそのときの戻り先アドレスは解放されます。
永久に自分自身を呼び出すとスタックオーバーフローというエラーになるのは、積上げっぱなしで解放されないスタック領域が不足するために起こるエラーです。

なかなか文章だけで説明するのは難しいのであとは「コールスタック」で調べてください。

関数の引数やローカル変数などもこのスタックを利用して記憶しています。

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

+3

bool retItem(int arr[],int start, int end,int key) {
    for (; start < end; start++) {
        if (arr[start] == key) return true;
    }
    return false;
}


例示されたコードは末尾再帰って言って、ループに直せます。
コンパイラオプションを適切に設定すると、再帰じゃなくて、ただのループに最適化されます。
このコードは、array が 2 万個くらい要素があるとスタックオーバーフローで落ちます。
再帰は呼び出し位置をスタックに記録して自身を呼び出すので、8 * 20000 で 160kb か、、、、
2万くらいじゃ落ちませんね。。。。どっちにしても、再帰を使わないで実装するとコードの安全性が高まります。問題無ければループ展開した方が良いですよ。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

checkベストアンサー

+1

まず、他の関数の戻り値が、自分の関数の値になる場合を確認します。
g() { a = f(); rerutn a; }
なら、関数 f() が return した値(true, false, 10, "hello" など様々な場合がある)が変数 a に代入され、それが関数 g() の return 値になります。変数 a を省略して
g() { return f(); }
と書けることもお分かりですよね。これは次の、再帰関数の動作を理解する基本なので、念のため。

例に挙げられた再帰関数の場合。再帰関数の動きを理解しようという時は
簡単で具体的なデータを想定し、動作をトレースしてみると良いと思います。例えば、
array[] = { 5, 1, 7 };
として、retrieveItem(array, 0, 2, 5) を呼び出したとします。
この場合は、array[0] == 5 なので、ただちに return true; となります。

では、retrieveItem(array, 0, 2, 4)はどうなるか。
array[0]~array[2]に4は無いので false が返るはずですよね。

この時、retrieveItem(array, 0, 2, 4) は、関数内の二つのif条件がともに成立しないので
return retrieveItem(array, 1, 2, 4) を実行します。
この時、関数呼出しが起こりますが、第二引数が変化(0→1)した事をお忘れ無く。
同様に、
retrieveItem(array, 0, 2, 4)

retrieveItem(array, 1, 2, 4)

retrieveItem(array, 2, 2, 4)

retrieveItem(array, 3, 2, 4)

と、次々に関数 retrieveItem() の呼出しが起こります。
このような事を関数呼出しがネストする等と言います。

最後のretrieveItem(array, 3, 2, 4)に来たところで、二つめのif条件が成立して
return false; を実行します(こういう条件を再帰関数の終了条件などと呼ぶ。
再帰関数の中に終了条件が無いと、どこまでもネストしてスタックオーバーフローする)。

さて、ここで return した値 false は、どうなるか。
いきなりretrieveItem(array, 0, 2, 4)の return 値になるのではありません。
retrieveItem(array, 2, 2, 4) が呼出した retrieveItem(array, 3, 2, 4);
の値として返る(retrieveItem(array, 3, 2, 4)の値になる)のです。

従って、次はretrieveItem(array, 2, 2, 4) が false を返すことになります。
つまり、再帰の終了条件でreturnされた値 false は、
retrieveItem(array, 0, 2, 4)

retrieveItem(array, 1, 2, 4)

retrieveItem(array, 2, 2, 4) 

retrieveItem(array, 3, 2, 4) ←ここで return false;

という順序で逆向きに返り、最終的にretrieveItem(array, 0, 2, 4)の値になります。
これが再帰と return の動作です。

なお、関数が自分自身を呼ぶ、という事が分かりにくいと思うなら「関数の中身は同じだが、違う名前の関数がたくさんある」と想像するのも手です。例えば retrieveItem(array, 0, 2, 4)の中では
 return retrieveItem1(array, 1, 2, 4); 等と想像して、
retrieveItem(array, 0, 2, 4)→retrieveItem1(array, 1, 2, 4)→retrieveItem2(array, 2, 2, 4)→retrieveItem3(array, 3, 2, 4)と、どんどん別の名前の関数を呼び出す、と考えるのです。それぞれの関数は、別の関数が返した値を自分の戻り値として返すのです。

returnを一度すると、ループから抜けてしまうという事ですよね

この場合、ループから抜ける、とは再帰の終了条件に到達する事ですが、再帰呼出しはループではないので不正確ですね。最適化した結果、再帰をループに書き直す場合もあるでしょうが、コンパイラはそのまま再帰呼出しのコードを生成するようです。

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

0

こんにちは。

いままであまり考えずにreturnを使っていたのですが、returnを一度すると、ループから抜けてしまうという事ですよね。 

まず、話がややこしくならないよう、再帰呼び出しの場合に限定して説明します。(再帰でない通常のケースは不要ですよね?)

提示されたソースでは、retrieveItem()を再帰的に呼び出してますが、return retrieveItem(略);以外の再帰呼び出しがありません。従って、retrieveItem()から戻っくると直ぐにreturnします。なので、一度returnすると再帰呼び出しによるループから抜けます。

なお、例えば、ツリーサーチでよく使われる深さ優先探索(DFS)では必ずしもreturnを1度するとループを抜けるとは限りません。
「葉」に達するとreturnしますが、枝の分岐点まで戻ると次の枝をサーチするので、継続して探索関数を呼び出します。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

0

基本的Returnはふたつ方法として使えます。
1.値を返す。
2.なにも返すじに関数から抜ける。
例えばー
bool myfunc(bool a){
a=false;
return a;
}
この場合はFalseを返す。
2.
void assign(){
return;
int a[100];
int i=0;
for(i=0;i<99;i++){
a[i]=i;
}
}
この場合は関数はなにも返さない。reuturnのあとの処理もしない。
頑張って。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

0

例えばStart,Endが1~5で、arrayの3番目でkeyが見つかる場合の流れを考えると

(retrieveItem初回呼出)
・retrieveItem(array,1,5,key)を処理
・start=1でkeyは見つからずreturn retrieveItem(array,2,5,key)を処理

    (retrieveItem再帰1)
    ・start=2でkeyは見つからずreturn retrieveItem(array,3,5,key)を処理

        (retrieveItem再帰2)
        ・start=3でkeyが見つかる。return Trueを返す。

    ・retrieveItem(array,3,5,key)がTrueなのでreturn retrieveItem(array,3,5,key)はreturn Trueとなる。

・retrieveItem(array,2,5,key)がTrueなのでreturn retrieveItem(array,2,5,key)はreturn Trueとなる。


という流れで、結果として初回に呼び出したretrieveItemがTrueで終了することになります。

同様にkeyが見つからないままstart>endとなるまで再帰処理を重ねた場合、start>endとなったところでreturn Falseとなります。
その後の動きは上記と同様で、1階層づつ戻っていき最終的には最初に呼び出したretrieveItemがFalseで終了することになります。

質問とは関係ありませんが、この判定の仕方だと例えばStart=1,End=5で処理をした場合で、arrayの6番目でキーが一致する場合、Trueになってしまう気がします。
Start~Endの範囲でチェックしたいのであれば(start > end)の判定を(array[start] == key )の判定より先に行うか、(start+1 > end)で判定する必要があると思います。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

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

関連した質問

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