網絡学習管理 速習C言語入門3 C exercises(b) Recursive call

C exercises(b) Recursive call

東京魅力PRサークル会員募集中

http://svn.mki.biz/pukiwiki/index.php?u-tokyo

興味があれば、ぜひコメントください。

階乗の計算

皆さんは「階乗の計算」を覚えていますか? 5の階乗なら「5!」と表記し,

5! = 5 × 4 × 3 × 2 × 1

と計算します。つまり答えは120です。

0 の階乗:1
1 の階乗:1
2 の階乗:2 × 1
3 の階乗:3 × 2 × 1
– – – – – – –
n の階乗: n × (n – 1) × (n – 2) – – – 3 × 2 × 1
– – – – – – –

方法1)掛け算を続けることで階乗を求め

n! = n × (n-1) × (n-2) .. × 1

#include <stdio.h>

long Factorial1(int n) ;
long Factorial2(int n) ;
void main(void);

  /* 階乗を求める(非再帰版) */
long Factorial1(int n)
 {
    long p = 1L;

    if (n < 2)       /* nが0か1なら */
        return (1L); /* 1を返す */
    else if (n > 1) {
        for ( ; n > 0; n--)
            p = p * n;
            return (p);
    }
}	


void main(void)
{
    int n;
    long f;

    printf("整数を入力して下さい\t");
    scanf("%d", &n);

    f = Factorial1(n);
    printf("Factorial1(  ) = %ld\n", f);

}

 

方法2)関数の中から自分自身を呼び出す

再帰呼び出し (recursive call)とは,関数の中から自分自身を呼び出すプログラミングのテクニックです。再帰呼び出しで階乗の計算式を考えてみると,

n! = n × (n-1)!

と定義できることがわかるでしょうか。

#include <stdio.h>

long Factorial1(int n) ;
long Factorial2(int n) ;
void main(void);

  /* 階乗を求める(再帰版) */
long Factorial2(int n)
 {
    if (n < 2)        /* nが0か1なら */
        return (1L);  /* 1を返す */
    else              /* nに自分より1小さい自分を掛ける */
        return (n * Factorial2(n -1));
}

void main(void)
{
    int n;
    long f;

    printf("整数を入力して下さい\t");
    scanf("%d", &n);

    f = Factorial2(n);
    printf("Factorial2(  ) = %ld\n", f);
}

再帰呼び出しを使う上で、大切なポイントが2つあります。

 

 1.終着点があること

呼び出しが無限に繰り返されてはなりません。再帰とは再び帰ってくるということ。そのためには終着点が必要になります。nの階乗はn=1が終着点です。

 

 2.関数を抜けるときは元に戻す

グローバルな変数を用いて状態を把握している場合、関数を抜けるときは関数に入ったときの状態に必ず戻すようにして下さい。そうしないと探索の整合性が失われてしまいます。

 再帰は使うべきか

一般に次のことが言えます。

  • 再帰プログラムは計算機に負荷をかけるプログラムである。
  • 時によっては,膨大な負荷をかけることもある。
  • 簡単に非再帰プログラムとして書けるものは再帰プログラムを使うべきではない。

それでも,再帰プログラムが基本的であると言われるのは何故でしょうか。それは再帰プログラムが大きな力を秘めているからです。つまり

  • 再帰プログラムでは簡単に書けるが,非再帰プログラムはかなり複雑なプログラムになってしまうようなものがある。

ということです。

このような問題が意外とあるのです。再帰プログラム技法を,身につけたら,プログラミングを行う際,次のような視点で考えるのが良いかもしれません。

  • まずは,非再帰プログラムで問題を考えてみる。
  • 難しいと判断した場合,再帰プログラムで考えてみる。

再帰が有効な例

  • ハノイの塔
  • データの木構造, 入れ子構造
  • XML文書
  • ファイルシステム

演習

再帰呼び出しの方法で、整数を二進数で表示するプログラムを作成

/*
実行例

12345678
101111000110000101001110

*/

ヒント

void print_binary(unsigned int n)
{
    if (n >= 2) print_binary(n/2);
    printf("%d", n%2);
}

 

1 thought on “C exercises(b) Recursive call”

Leave a Reply

Your email address will not be published. Required fields are marked *

CAPTCHA


Related Post

C exercises(e) ExamC exercises(e) Exam

下記の演習サイトに、ミニテストを行ってください ログインID :  15TE123  パスワード: 15TE123@ueno.daiichi-koudai.ac.jp http://lms.chenlab.net/ (http://lmspress.net/) — メインサイト http://lms2.chenlab.net/ — ミラーサイト、演習専用 http://lms3.chenlab.net/ — ミラーサイト、演習専用

C programming exercisesC programming exercises

【授業の概要】 コンピュータプログラム開発言語の中で広く利用されているC言語をCプログラミング開発環境ソフト: CPad for Borland C++ Compilerを使った一人一台のPCを使い実習により学びます. 毎回問題に取り組み理解を深めます。復習問題としてプログラミング課題を出題する。 【授業要旨】 回数 題目 授業内容 学習課題 予習時間(分) 復習時間(分) 1 ガイダンス 学習目的 C言語プログラミングⅡの試験解説   C言語検定試験について 授業内容を復習する 60 […]

C exercises(d) Scope and Storage classC exercises(d) Scope and Storage class

変数の通用範囲 自動変数のことを局所変数、外部変数のことをグローバル変数(大域変数)ともいいます。 変数のスコープの範囲を図で表してみます。 赤色で囲った部分がグローバル変数の有効範囲です。 青色で囲った部分がローカル変数の有効範囲です。 この図ではローカル変数の寿命を関数内と説明しましたが、正確にはブロック内です。 ブロックとは、{}で囲まれている範囲のことを指しています。 記憶クラス Cで扱う記憶領域は一般に、プログラム領域、静的領域、スタック領域、ヒープ領域の 4つに大別されます。 記憶クラスには、4つあり、自動、静的、外部、レジスタがあります。 記憶クラス 記憶領域 スコープ 記憶クラス指定子 自動変数 スタック { } の内側 […]