質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.51%

  • C

    3684questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

再帰関数の見方、理解の仕方について

解決済

回答 2

投稿

  • 評価
  • クリップ 1
  • VIEW 298

tomokon

score 5

以前質問し、回答して頂きましたtomokonです。その節はお世話になりました。
今回はソースコードについてではなく、考え方について教えていただきたく思い、質問させて頂こうと伺いました。

再帰関数の動きについて、うまくイメージができません

再帰関数を使ったプログラムを今作っているのですが、どうにも頭の中でうまく想像することができません。そこで質問なのですが、皆さまはどのように考えたりしてプログラムの理解をされているのでしょうか?
例として、順列組み合わせのコードを挙げます。

該当のソースコード

#include <stdio.h>

void  list(int t[])
{
    int i;

    for(i = 0; i < 4; i++){
        printf("%d ",t[i]);
    }

    printf("\n");
}

// 順列を求める
void  jyun(int t[], int n)
{
    int i, k, w;

    if (n < 2){
        list(t);
        return;
    }

    k= n-1;

    for(i = n - 1; i >= 0; i--){   
    w = t[k];
        t[k] = t[i];
        t[i] = w;
        jyun(t, k);

    printf("%d %d\n", t[i], t[k]);

        t[i] = t[k];
        t[k] = w;
    }
    return;
}

int  main()
{   
    int i, tbl[4];

    for(i = 0; i < 4; i++){
        tbl[i] = i + 1;
    }   

    jyun(tbl, 4);

    return(0);
}

試したこと

紙に配列tblがどのように変化したかを書いたのですが、書いていく内に数が多くなり、どの配列の部分にどの変数が入ってどういう数が格納されたか、今プログラムのどの部分にいるのかとこんがらがってしまいました。
以前アドバイスして頂いたように図を書いてみようかとも思ったのですが、どういう風に図を書いていいのかがまず分からず、行き詰ってしまいました。
熟練者の皆様はこういった関数を理解する時にどのように考えられているのか、是非、教えていただければと思います。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+1

  • 全部一度に展開しようとせずに、まず前後の呼び出しとの関係性を見る。
  • 終了条件から見る。

とわかりやすくなります。


今回の場合は、再帰呼び出ししなくなるときはn=1です:jyun(t,1)
やることは、
tを表示します。

次にn=2を考えてみます:jyun(t,2)
このとき、k=1、i=1,0です。
やることは、各iについて
t[k]とt[i]を入れ替えて、jyun(t,1)を呼び出し、t[k]とt[i]を入れ替えます。
t={a,b,c,d}だったとすると、
jyun({a,b,c,d},1)
jyun({b,a,c,d},1)
を呼び出して、
tはt={a,b,c,d}に戻ります。

次にn=3を考えてみます:jyun(t,3)
このとき、k=2、i=2,1,0です。
やることは、各iについて
t[k]とt[i]を入れ替えて、jyun(t,2)を呼び出し、t[k]とt[i]を入れ替えます。

t={a,b,c,d}だったとすると、
jyun({a,b,c,d},2)
jyun({a,c,b,d},2)
jyun({c,b,a,d},2)
を呼び出して、
tはt={a,b,c,d}に戻ります。
(jyun(t,2)の呼び出し前後でtの順番は元通りになるので、
結局jyun(t,3)の呼び出し前後でも順番は元通りになります。)

n=4も同様に考えると
jyun({a,b,c,d},3)
jyun({a,b,d,c},3)
jyun({a,d,c,b},3)
jyun({d,b,c,a},3)
を呼びます。

今までの結果から
例えばjyun({a,b,c,d},3)を展開していくと

jyun({a,b,c,d},3)
    jyun({a,b,c,d},2)
        jyun({a,b,c,d},1)
            {a,b,c,d}を表示
        jyun({b,a,c,d},1)
            {b,a,c,d}を表示
    jyun({a,c,b,d},2)
        jyun({a,c,b,d},1)
            {a,c,b,d}を表示
        jyun({c,a,b,d},1)
            {c,a,b,d}を表示
    jyun({c,b,a,d},2)
        省略

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/11/01 00:50

    回答ありがとうございます。
    丁寧な解説で分かりやすく、とてもためになりました。是非参考にさせていただき、理解に努めます。それと仰っていた二点については特に意識するようにし、今後に活かせていきます。

    キャンセル

+1

設計は慣れだと思います。
解析はツールがあるんで活用するとイイですよ。

http://pythontutor.com

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/11/01 00:54

    回答ありがとうございます。
    回数をこなし、早く設計になれるようにしたいと思います。また、ツールについては全く失念していました。
    一応BCC Developer 1.2.21についているデバッガを使い、変数や配列の追跡を試してはみたのですが、どうにも使い辛くそちらの方は諦めてしまっていました。
    今後はご紹介いただいたツールは勿論、他のも見て活用していきます。

    キャンセル

  • 2017/11/01 01:22

    トータルで見たときには当然デバッガのほうが性能が良いですけど、こと再帰の挙動に関しては、リンク先のツールが1番理解しやすかったです。
    目的に合わせて使い分けてください。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.51%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • C

    3684questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。