応用情報技術者試験 - SE娘の剣 -

応用情報処理技術者試験の対策サイトです。 応用情報処理技術者試験の午前問題を中心とした基礎用語の解説を中心に掲載します。書き始めたばかりなので、内容はまだまだ不十分です。少しずつ追記していきます

再帰アルゴリズム

 

1.再帰とは

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

f:id:mamori_yuto:20181103063502j:plain

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

sm.seeeko.com

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

(1)H29秋AP午前問7

問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
これの、再帰的に書く方です。

(2)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を表示
  の3段階。
 
  したがって、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を表示
  という処理になる。