再帰呼び出し　解答ページ | Programming Place Plus　Ｃ言語編　第５３章

トップページ – Ｃ言語編 – 第５３章

問題① 🔗

問題①　階乗を計算する関数を再帰呼び出しを利用して作成してください。また、再帰呼び出ししない方法でも作成してください。


まずは再帰版から。

#include <stdio.h>
#include <assert.h>

int fact(int n);

int main(void)
{
    int num = 5;
    printf("%d! = %d\n", num, fact(num));
}

/*
    階乗を計算する
    引数:
        n:  階乗n! の n にあたる数。
    戻り値:
        階乗n! の結果。
*/
int fact(int n)
{
    assert(n >= 0);

    if (n == 0) {
        return 1;
    }

    return fact(n - 1) * n;
}

実行結果：

5! = 120

階乗を再帰呼び出しで計算するプログラムは、再帰呼び出しを学ぶ際の通過儀礼のようなものですが、実用性は皆無と言えます。なぜなら、次のように素直に繰り返しで実装した方が効率的だからです。

#include <stdio.h>
#include <assert.h>

int fact(int n);

int main(void)
{
    int num = 5;
    printf("%d! = %d\n", num, fact(num));
}

/*
    階乗を計算する
    引数:
        n:  階乗n! の n にあたる数。
    戻り値:
        階乗n! の結果。
*/
int fact(int n)
{
    assert(n >= 0);

    int ans = 1;

    for (int i = 1; i <= n; ++i) {
        ans *= i;
    }

    return ans;
}

実行結果：

5! = 120

再帰呼び出しの方は、関数の呼び出しにかかる処理時間や、スタック領域の使用量の増加につながりますから、この程度の処理に再帰呼び出しを持ち出すのは、一般的には無駄です。それでも、再帰呼び出しのプログラムを書く練習としては良い題材なので、経験しておくのは良いことでしょう。


問題② 🔗

問題②　次のようなプログラムがあります。

#include <stdio.h>

struct Data_tag {
    int num;
    struct Data_tag* next;
};

static struct Data_tag g_head;

int main(void)
{
    struct Data_tag data00;
    struct Data_tag data01;
    struct Data_tag data02;

    g_head.num = 0;
    g_head.next = &data00;

    data00.num = 15;
    data00.next = &data01;

    data01.num = 30;
    data01.next = &data02;

    data02.num = 45;
    data02.next = NULL;
}

Data_tag構造体のメモリアドレスを渡すと、ヌルポインタに行き着くまで nextメンバをたどっていき、その過程で numメンバの内容を出力する関数を作成してください。再帰呼び出しを使ったものと、使わないものをそれぞれ作成してください。


ポインタによって、次のデータを結び付けています。これは、線形リストと呼ばれるデータ構造の一種で、実用上にも非常に価値があるものです。詳細は、アルゴリズムとデータ構造編【データ構造】第３章を参照してください。

データの終端を表すために、最後のポインタには NULL を入れてありますから、ここまでたどっていけばいいということになります。

まずは再帰版です。

#include <stdio.h>
#include <assert.h>

struct Data_tag {
    int num;
    struct Data_tag* next;
};

static struct Data_tag g_head;

void print_data(const struct Data_tag* data);


int main(void)
{
    struct Data_tag data00;
    struct Data_tag data01;
    struct Data_tag data02;

    g_head.num = 0;
    g_head.next = &data00;

    data00.num = 15;
    data00.next = &data01;

    data01.num = 30;
    data01.next = &data02;

    data02.num = 45;
    data02.next = NULL;


    puts("start by gData");
    print_data(&g_head);

    puts("start by data01");
    print_data(&data01);
}

void print_data(const struct Data_tag* data)
{
    assert(data != NULL);

    if (data->next == NULL) {
        return;
    }

    printf("%d\n", data->num);
    print_data(data->next);
}

実行結果：

start by gData
0
15
30
start by data01
30

nextメンバに格納されているポインタをたどっていかないといけないことに注意してください。++演算子でインクリメントしていくのではありません（++ で次に進むことができるのは、配列のようにメモリ上で連続的に並んでいる場合だけです）。再帰呼び出しを終えるタイミングは、これ以上たどれなくなったときなので、nextポインタがヌルポインタになったときです。

再帰呼び出しをしない方法でも簡単に作れます。関数の部分だけ取り上げます（他はまったく同じです）

void print_data(const struct Data_tag* data)
{
    assert(data != NULL);

    const struct Data_tag* p = data;

    while (p->next != NULL) {
        printf("%d\n", p->num);
        p = p->next;
    }
}


参考リンク 🔗


更新履歴 🔗

≪さらに古い更新履歴≫

　「NULL」よりも「ヌルポインタ」が適切な箇所について、「ヌルポインタ」に修正。

　全面的に文章を見直し、修正を行った。
章のタイトルを変更（再帰 -> 再帰呼び出し）

　新規作成。


第５３章のメインページへ

Ｃ言語編のトップページへ

Programming Place Plus のトップページへ

はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポスト／フォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る