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

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

新規登録して質問してみよう
ただいま回答率
85.50%
C

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

Q&A

解決済

2回答

1926閲覧

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

tomokon

総合スコア13

C

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

0グッド

1クリップ

投稿2017/10/31 04:42

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

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

###該当のソースコード

C

1#include <stdio.h> 2 3void list(int t[]) 4{ 5 int i; 6 7 for(i = 0; i < 4; i++){ 8 printf("%d ",t[i]); 9 } 10 11 printf("\n"); 12} 13 14// 順列を求める 15void jyun(int t[], int n) 16{ 17 int i, k, w; 18 19 if (n < 2){ 20 list(t); 21 return; 22 } 23 24 k= n-1; 25 26 for(i = n - 1; i >= 0; i--){ 27 w = t[k]; 28 t[k] = t[i]; 29 t[i] = w; 30 jyun(t, k); 31 32 printf("%d %d\n", t[i], t[k]); 33 34 t[i] = t[k]; 35 t[k] = w; 36 } 37 return; 38} 39 40int main() 41{ 42 int i, tbl[4]; 43 44 for(i = 0; i < 4; i++){ 45 tbl[i] = i + 1; 46 } 47 48 jyun(tbl, 4); 49 50 return(0); 51}

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

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ベストアンサー

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

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


今回の場合は、再帰呼び出ししなくなるときは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/10/31 06:41

ozwk

総合スコア13512

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

tomokon

2017/10/31 15:50

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

0

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

http://pythontutor.com

投稿2017/10/31 04:53

退会済みユーザー

退会済みユーザー

総合スコア0

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

tomokon

2017/10/31 15:54

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

退会済みユーザー

2017/10/31 16:22

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問