C言語プログラミングの再帰がいまいちわかりません。 int rec(int n) { if (n =

C言語プログラミングの再帰がいまいちわかりません。

int rec(int n)
{
if (n == 1)
return 5;
else
return 3 * rec(n - 1) + 4;
}
int main(void)
{
int n;
printf("Input n>");
scanf("%d", &n);
printf("rec(%d)=%d\n", n, rec(n));
int i, an;
for (an = 5, i = 1; i < n; i++)
an = 3 * an + 4;
printf("sol=%d\n", an);
return 0;
}

このプログラムはa1が5
a（n+1）=3(n)+4の漸化式を表しているようです。
どのようにrec関数が動いているのか？
段階踏んで詳しく教えてください。
よろしくお願いします。

※分かりやすいようにa=3(n-1)+4にしています。がこのように変型しても大丈夫ですよね？なぜでしょう？

No.1 回答者： cametan_42 回答日時： 2018/10/19 21:16

> C言語プログラミングの再帰がいまいちわかりません。

質問がいまいちわかりません。

> a（n+1）=3(n)+4の漸化式を表しているようです。

「表しているようです」もクソも、プログラミング用語で「漸化式」の事を「再帰」と呼ぶのです。
漸化式 = 再帰、です。
大事なことなんで二度言いました。

> どのようにrec関数が動いているのか？
> 段階踏んで詳しく教えてください。

ハッキリ言うけど、「段階を踏んで再帰を理解しよう」なんてするから分からなくなるんです。
「再帰の動きをトレースして考える」なんぞ無駄なんです。
(もっとハッキリ言うけど、プログラミング教育はクッソくだらねぇ無駄な事を学生に強いています)
高校時代の数学を思い出して下さい。「漸化式を理解しようとして」一々n=0からスタートして逐次計算して追っかけていきましたか?んな事やってませんよね。

ある種、次のような諦めが必要です。

・再帰がキチンと計算出来るかどうか、はコンパイラ、ないしはインタプリタの役割/仕事なんでユーザーが気にかける必要はない

再帰が動くかどうかはコンパイラやインタプリタの責任であって、貴方の責任じゃないのです。もっと言うと「プログラミングを勉強している」学生の責任でもないですし、「再帰を書こうとする」プログラマの責任でもない。これも大事な事なんで二度言いました。
そんな事に関して「内部動作は・・・」なんぞ考えるのは無駄です。考えさせようとするのは、クッソくだらない事で時間つぶして、単位を学生に与えるのを簡単にしないため、です。
重要なのはむしろこっちです。

・貴方が再帰でプログラムを書けるか否か

と言う事です。要するに「貴方が漸化式を自在にでっち上げられるか否か」と言う事ですね。
これは良い練習方法がある。高校時代に使った数学の練習問題を用意する。それで数列の項目で「漸化式を解く」問題の漸化式を「解かないで」いいので、そのままC言語プログラミングへ「機械的に」翻訳する。
ぶっちゃけ10問もやれば「再帰ってバカバカしいくらいに簡単だ」と思うようになります。
「考える」必要はないです。必要なのは「機械的にプログラミングへと翻訳する」練習です。
「再帰が分からない」のは圧倒的に練習量が少ないだけ、なんですよ、事実上は。内部動作を考える暇があったら高校の数学の問題集を利用しなさい。それが一番です。

No.2 回答者： k-841 回答日時： 2018/10/20 03:04

＞どのようにrec関数が動いているのか？

簡単に言えば、一旦引数が1になるまで再帰関数の奥まで潜り続け、一番奥から最初に戻ってゆく過程でそのreturn値を使って順に計算をする、ということです。

なので、

＞このように変型しても大丈夫ですよね？

その理解で大丈夫です。

ちなみに、ミッションクリティカルな用途で使われるプログラムでは関数の再帰呼び出しは使うべきではないと考えています。一応私もプロの端くれですが、社内のプログラマには関数の再帰呼び出しは絶対に使ってはいけないと教育しています。

理由は次の通りです。
・関数の再帰呼び出しは必ずループで置き換えられる
・関数の再帰呼び出しは（というか、関数呼び出しは）、呼び出されるごとにスタック領域という関数呼び出しごとにその関数の情報を保存している領域に値を保存するため、呼び出し回数に比例してメモリを消費する（ループで実装した場合、途中で動的にメモリ確保するような処理でない限り、使用メモリ量はどれだけループを回っても一定です）
・関数の再帰呼び出しは、呼び出される回数が多いとメモリ不足に陥り、プログラムが異常終了する

試しにscanf()で入力するときに大きな値を入れてみてください。ある値以上になるとプログラムが途中で強制終了してしまいます。この「ある値」は、処理系や再起関数で保持すべきメモリの量に依存するため一概には言えませんが、質問文のプログラムを私の手元の古い32ビットパソコンで試したところ、2396501以上で異常終了しました（もっとも、この問題であればそれよりも小さい数字で桁あふれして正確に計算できないので、問題ないと言えば問題ないのですが・・・）。

また、実行時間も、ギリギリ異常終了しない2396500だと、関数の再帰呼び出しを使わない場合は約0.05秒なのに対して、関数の再帰呼び出しを使う場合は約0.9秒と、20倍近くも速度差が出ました。

No.3 回答者： siffon9 回答日時： 2018/10/20 06:33

できるだけ簡潔に回答します。

例として、n = 3の場合を考えます。

main 実行中　　mainでrec(3)を実行する。
rec(3)実行中　　　　rec(3)の戻り値は、3*rec(2)+4、ここでrec(2)実行し値を求める。
rec(2)実行中　　　　　　rec(2)の戻り値は、3*rec(1)+4、ここでrec(1)実行し値を求める。
rec(1)実行中　　　　　　　　5を戻り値として返す。
rec(2)実行中　　　　　　3*rec(1)+4 = 3*5+4 = 19を戻り値として返す
rec(3)実行中　　　　3*rec(1)+4 = 3*19+4 = 61を戻り値として返す
main 実行中　　戻り値は、51

このようにmainの中でrec(3)を実行し
rec(3)の関数中で、rec(2)を実行し、
rec(2)の関数中で、rec(1)を実行する。

という様に値n=1になるまで、自身を呼び出して
その戻り値を使って自身の戻り値を計算しています、

以上、ご参考になれば幸いです。