１．再帰とは

「再帰」とは、「再び帰ってくる」ですが、どこに帰ってくるかというと、自分自身です。
過去問（H29春AP問7を部分的に抜粋）では、「再帰的プログラムは，手続の中でそれ自体を呼び出すプログラム」とあります。

f:id:mamori_yuto:20181103063502j:plain

以下に、再帰的（リカーシブ）、再入可能（リエントラント）などを含めて解説しています。

sm.seeeko.com

２．過去問および再帰的なプログラムの具体例

（１）H29秋AP午前問７

問7　fact(n)は，非負の整数nに対してnの階乗を返す。fact(n)の再帰的な定義はどれか。
ア　if　n=0　then　return　0　else　return　n×fact(n-1)
イ　if　n=0　then　return　0　else　return　n×fact(n+1)
ウ　if　n=0　then　return　1　else　return　n×fact(n-1)
エ　if　n=0　then　return　1　else　return　n×fact(n+1)

【正解】ウ

fact(1)=1
fact(2)=2×fact(1)=2×1=2
fact(3)=3×fact(2)=3×2×1=6
fact(4)=4×fact(3)=4×3×2×1=24

たとえばn=3とすると
fact(3)=3×fact(2)
fact(2)=2×fact(1)
fact(1)=1×fact(0)
fact(0)= ←ここを0にしてしまってはダメで、1にすべき。
そうしないと
fact(3)=3×2×1×0=0になってしまう。

実際のプログラムは、以下に記載しました。
 

sm.seeeko.com

http://sm.seeeko.com/archives/65924343.html
これの、再帰的に書く方です。

（２）H25秋AP

問8　再帰的に定義された手続procで，proc(5)を実行したとき，印字される数字を順番に並べたものはどれか。
　　　　　proc(n)
　　　　　　n=0ならば戻る
　　　　　　そうでなければ
　　　　　　{
　　　　　　　nを印字する
　　　　　　　proc(n-1)を呼び出す
　　　　　　　nを印字する
　　　　　}
　　　　　を実行して戻る

ア　543212345
イ　5432112345　　
ウ　54321012345　　
エ　543210012345

【正解】イ

実際のプログラムは以下

#include<stdio.h> // stdio.h（標準入出力を行うための関数が定義されたファイル）を読み込む

// proc関数。整数を一つ（int n）受け取って処理を行い、処理後に値は返さない（void）
void proc(int n) {
    if (n == 0) // もしnが0なら
        return; //   何もせず戻る
    else        // そうでなければ（nが0以外なら）
    {
        printf("%d", n); // nを表示
        proc(n-1);       // proc(n-1)を実行
        printf("%d", n); // nを表示
    }
}

// main関数。引数は取らない。処理後に値を返さない
void main() {
    proc(5);
}


補足解説
  proc(n)の流れは
  　　・nを表示
  　　・proc(n-1)を実行
  　　・nを表示
  の３段階。
 
  したがって、proc(5)を呼び出すと、
  　　・5を表示
  　　・proc(4)を実行
  　　・5を表示
 
  proc(4)の処理は
  　　・4を表示
  　　・proc(3)を実行
  　　・4を表示
  

  これを続けていくと、
  　　・5を表示
   　　・4を表示
　　  　　・3を表示
　 　  　　・2を表示
　　    　　・1を表示
 　　    　　・proc(0)を実行
  　  　　　・1を表示
  　　 　　・2を表示
  　　　　・3を表示
   　　・4を表示
  　　・5を表示

  proc(0)は何もせずにreturnするため、
  最終的に、
    　　・5を表示
   　　・4を表示
　　  　　・3を表示
　 　  　　・2を表示
　　    　　・1を表示
  　  　　　・1を表示
  　　 　　・2を表示
  　　　　・3を表示
   　　・4を表示
  　　・5を表示
  という処理になる。