再帰呼び出し(練習問題の解答例)

| Topic path: Top / 授業 / C言語基礎 / 再帰呼び出し(練習問題の解答例)

*フィボナッチ数 [#l160d072]

定義をそのままswitch文で書くと、次のようになります。
#geshi(c){{
int f(int n) {
  switch (n) {
  case 1:
  case 2:
    return 1;
  default:
    return f(n - 2) + f(n - 1);
  }
}
}}
このswitch文では、return文で戻り値を返してしまうので、break文は要りません。

大きな数のフィボナッチ数を求めたいときは、戻り値をunsigned long型にしましょう。

ちなみに、この関数を使ってフィボナッチ数 [math]f_{10}[/math] を求めるためのmain関数は次のようになります。
#geshi(c){{
int main(void) {
  printf("%d\n", f(10));
  return 0;
}
}}


*ユークリッドの互除法 [#z37e526d]
#geshi(c){{
/*
 * ユークリッドの互除法
 * ただし a > b >= 0
 */
int gcd(int a, int b) {
  return b == 0 ? a : gcd(b, a % b);
}
}}

ちなみに、この関数を使って 84 と 49 の最大公約数を求めるmain関数は次のようになります。
#geshi(c){{
int main(void) {
  printf("%d\n", gcd(84, 49));
  return 0;
}
}}

*基数変換 [#e4f7c5ed]

#geshi(c){{
/*
 *  10進数を2進数に基数変換して出力する
 */
void radconv(int n) {
  if (n > 1) { radconv(n / 2); }
  printf("%d", n % 2);
}
}}

再帰呼び出しと最下位ビットの出力の順序に気をつけましょう。

int型とint型の除算 / の結果はint型になるため、n / 2 の余りが無視されることを利用しています。

ちなみに、この関数を使って10進数 65 を2進数に変換して出力するmain関数は次のようになります。
#geshi(c){{
int main(void) {
  radconv(65);
  return  0;
}
}}


*ハノイの塔 [#a7db2ef2]

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS