returnの仕組み

Question

再呼のコードで、値が見つかれば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);
}

Answer 1

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

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

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

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

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

Answer 2

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万くらいじゃ落ちませんね。。。。どっちにしても、再帰を使わないで実装するとコードの安全性が高まります。問題無ければループ展開した方が良いですよ。

Answer 3

まず、他の関数の戻り値が、自分の関数の値になる場合を確認します。
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を一度すると、ループから抜けてしまうという事ですよね

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

Answer 4

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

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

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

        (retrieveItem再帰２)
        ・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となります。
その後の動きは上記と同様で、１階層づつ戻っていき最終的には最初に呼び出したretrieveItemがFalseで終了することになります。

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

Answer 5

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

Answer 6

こんにちは。

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

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

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

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