学校で再帰を理解するのに大きな問題があります。教授がそれについて話しているときはいつでも、私はそれを理解しているように見えますが、自分で試してみるとすぐに、頭が完全に吹き飛ばされます.
私は一晩中ハノイの塔を解こうとしていたのですが、完全に頭がおかしくなりました。私の教科書は再帰で約 30 ページしかないので、あまり役に立ちません。このトピックを明確にするのに役立つ本やリソースを知っている人はいますか?
Confused
質問する
88548 次
20 に答える
633
5 本の花が入った花瓶を空にする方法は?
答え: 花瓶が空でない場合は、花を 1 つ取り出してから、4 つの花が入った花瓶を空にします。
4 本の花が入った花瓶を空にする方法は?
答え: 花瓶が空でない場合は、花を 1 つ取り出してから、花が 3 つ入っている花瓶を空にします。
3 本の花が入った花瓶を空にする方法は?
答え: 花瓶が空でない場合は、1 つの花を取り出してから、2 つの花が入った花瓶を空にします。
2 本の花が入った花瓶を空にする方法は?
答え: 花瓶が空でない場合は、花を 1 つ取り出してから、花が 1 つ入っている花瓶を空にします。
花が 1 本入っている花瓶を空にする方法は?
答え: 花瓶が空でない場合は、花を 1 つ取り出してから、花の入っていない花瓶を空にします。
花が入っていない花瓶を空にする方法は？
答え: 花瓶が空でない場合は、花を 1 つ取り出しますが、花瓶は空なので完了です。
それは繰り返しです。それを一般化しましょう：
N 個の花が入った花瓶を空にする方法は?
答え: 花瓶が空でない場合は、花を 1 つ取り出し、N-1個の花が入った花瓶を空にします。
うーん、コードでそれを見ることができますか?
void emptyVase( int flowersInVase ) {
if( flowersInVase > 0 ) {
// take one flower and
emptyVase( flowersInVase - 1 ) ;
} else {
// the vase is empty, nothing to do
}
}
うーん、for ループでそれを実行できなかったのでしょうか。
そうです、再帰は反復に置き換えることができますが、多くの場合、再帰の方がよりエレガントです。
木の話をしましょう。コンピュータ サイエンスでは、ツリーはノードで構成される構造であり、各ノードには、ノードでもあるいくつかの子、または null があります。二分木は、通常「左」と「右」と呼ばれるちょうど2つの子を持つノードで構成される木です。ここでも、子はノードまたは null にすることができます。ルートは、他のノードの子ではないノードです。
ノードがその子に加えて値、数値を持ち、あるツリーのすべての値を合計したいとします。
任意の 1 つのノードの値を合計するには、ノード自体の値をその左の子の値 (存在する場合) とその右の子の値 (存在する場合) に加算します。ここで、null でない場合、子もノードであることを思い出してください。
したがって、左の子を合計するには、子ノード自体の値を、その左の子の値 (存在する場合) とその右の子の値 (存在する場合) に加算します。
したがって、左の子の左の子の値を合計するには、子ノード自体の値を、左の子の値 (存在する場合) と右の子の値 (存在する場合) に加算します。
おそらく、あなたは私がこれでどこに行くのか予想していて、いくつかのコードを見たいと思っていますか? わかった：
struct node {
node* left;
node* right;
int value;
} ;
int sumNode( node* root ) {
// if there is no tree, its sum is zero
if( root == null ) {
return 0 ;
} else { // there is a tree
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
}
}
子が null かノードかを明示的にテストする代わりに、再帰関数が null ノードに対してゼロを返すようにしていることに注意してください。
たとえば、次のようなツリーがあるとします (数字は値、スラッシュは子を指し、@ はポインターが null を指すことを意味します)。
5
/ \
4 3
/\ /\
2 1 @ @
/\ /\
@@ @@
ルート (値が 5 のノード) で sumNode を呼び出すと、以下が返されます。
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;
その場で拡大してみましょう。sumNode が表示されているところはどこでも、return ステートメントの展開に置き換えます。
sumNode( node-with-value-5);
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;
return 5 + 4 + sumNode( node-with-value-2 ) + sumNode( node-with-value-1 )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + sumNode(null ) + sumNode( null )
+ sumNode( node-with-value-1 )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ sumNode( node-with-value-1 )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + sumNode(null ) + sumNode( null )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ 3 + sumNode(null ) + sumNode( null ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ 3 + 0 + 0 ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ 3 ;
return 5 + 4
+ 2 + 0 + 0
+ 1
+ 3 ;
return 5 + 4
+ 2
+ 1
+ 3 ;
return 5 + 4
+ 3
+ 3 ;
return 5 + 7
+ 3 ;
return 5 + 10 ;
return 15 ;
任意の深さと「分岐性」の構造を、複合テンプレートの繰り返し適用と見なすことで、どのように克服したかを見てください。sumNode 関数を使用するたびに、1 つの if/then 分岐を使用して 1 つのノードのみを処理し、2 つの単純な return ステートメントを使用して、仕様書から直接、それらの sleves をほぼ記述しましたか?
How to sum a node:
If a node is null
its sum is zero
otherwise
its sum is its value
plus the sum of its left child node
plus the sum of its right child node
それが再帰の力です。
上記の花瓶の例は、末尾再帰の例です。末尾再帰が意味するのは、再帰関数で再帰した場合 (つまり、関数を再度呼び出した場合)、それが最後に行ったことです。
ツリーの例は末尾再帰ではありませんでした。なぜなら、最後に行ったのは右の子の再帰でしたが、その前に左の子の再帰を行っていたからです。
実際、子を呼び出し、現在のノードの値を追加した順序はまったく問題ではありません。加算は交換可能だからです。
次に、順序が重要な操作を見てみましょう。ノードのバイナリ ツリーを使用しますが、今回は保持される値は数値ではなく文字になります。
ツリーには特別なプロパティがあります。どのノードでも、その文字は左の子が保持する文字の後に(アルファベット順で)、右の子が保持する文字の前に(アルファベット順で) 配置されます。
やりたいことは、ツリーをアルファベット順に出力することです。木の特殊な性質を考えると、それは簡単です。左の子、次にノードのキャラクター、次に右の子を出力するだけです。
勝手に印刷したいだけではないので、関数に印刷するものを渡します。これは print( char ) 関数を持つオブジェクトになります。どのように動作するかについて心配する必要はありません。print が呼び出されると、どこかに何かが出力されるだけです。
コードでそれを見てみましょう：
struct node {
node* left;
node* right;
char value;
} ;
// don't worry about this code
class Printer {
private ostream& out;
Printer( ostream& o ) :out(o) {}
void print( char c ) { out << c; }
}
// worry about this code
int printNode( node* root, Printer& printer ) {
// if there is no tree, do nothing
if( root == null ) {
return ;
} else { // there is a tree
printNode( root->left, printer );
printer.print( value );
printNode( root->right, printer );
}
Printer printer( std::cout ) ;
node* root = makeTree() ; // this function returns a tree, somehow
printNode( root, printer );
操作の順序が重要になることに加えて、この例は、再帰関数に何かを渡すことができることを示しています。私たちがしなければならない唯一のことは、各再帰呼び出しでそれを渡し続けることを確認することです。ノード ポインタとプリンタを関数に渡し、再帰呼び出しごとにそれらを「下に」渡しました。
ツリーが次のようになっているとします。
k
/ \
h n
/\ /\
a j @ @
/\ /\
@@ i@
/\
@@
何を印刷しますか？
From k, we go left to
h, where we go left to
a, where we go left to
null, where we do nothing and so
we return to a, where we print 'a' and then go right to
null, where we do nothing and so
we return to a and are done, so
we return to h, where we print 'h' and then go right to
j, where we go left to
i, where we go left to
null, where we do nothing and so
we return to i, where we print 'i' and then go right to
null, where we do nothing and so
we return to i and are done, so
we return to j, where we print 'j' and then go right to
null, where we do nothing and so
we return to j and are done, so
we return to h and are done, so
we return to k, where we print 'k' and then go right to
n where we go left to
null, where we do nothing and so
we return to n, where we print 'n' and then go right to
null, where we do nothing and so
we return to n and are done, so
we return to k and are done, so we return to the caller
したがって、印刷された行だけを見ると、次のようになります。
we return to a, where we print 'a' and then go right to
we return to h, where we print 'h' and then go right to
we return to i, where we print 'i' and then go right to
we return to j, where we print 'j' and then go right to
we return to k, where we print 'k' and then go right to
we return to n, where we print 'n' and then go right to
「ahijkn」と出力したことがわかりますが、これは確かにアルファベット順です。
単一のノードをアルファベット順に印刷する方法を知っているだけで、ツリー全体をアルファベット順に印刷することができます。これは、ノードの値を出力する前に左の子を出力し、ノードの値を出力した後に右の子を出力することを知っているだけです (私たちのツリーには、値をアルファベット順に後の値の左側に並べるという特別なプロパティがあったため)。
そして、それが再帰の力です: 全体の一部をどのように実行するかを知るだけで、すべてのことを行うことができます (そして、いつ再帰を停止するかを知ることができます)。
ほとんどの言語では、演算子 || を思い出してください。("or") は、最初のオペランドが true の場合に短絡します。一般的な再帰関数は次のとおりです。
void recurse() { doWeStop() || recurse(); }
リュック M のコメント:
SO は、この種の回答に対してバッジを作成する必要があります。おめでとう！
ありがとう、リュック！しかし、実際には、この回答を 4 回以上編集したため (最後の例を追加しますが、主にタイプミスを修正して洗練するためです。小さなネットブック キーボードで入力するのは難しいです)、これ以上ポイントを獲得できません。 . これは、将来の回答に多くの努力を払うことをいくらか思いとどまらせます。
それについての私のコメントを参照してください。
于 2009-04-04T21:19:46.340 に答える
37
無限再帰に陥ったので、あなたの脳は爆発しました。それはよくある初心者の間違いです。
信じられないかもしれませんが、あなたはすでに再帰を理解しているのです。あなたはただ、一般的ではあるが間違った関数の比喩に引きずり込まれているだけです。出入りするものが入った小さな箱です。
「ネットで再帰について詳しく調べる」など、タスクや手順の代わりに考えてください。それは再帰的であり、問題はありません。このタスクを完了するには、次のことを行う必要があります。
a）「再帰」のGoogleの結果ページを読む b) 読んだら、最初のリンクをたどって... a.1) 再帰に関する新しいページを読む b.1) 読んだら、最初のリンクをたどって... a.2) 再帰に関する新しいページを読む b.2) 読んだら、最初のリンクをたどって...
ご覧のとおり、長い間再帰的な処理を何の問題もなく行ってきました。
いつまでその仕事を続けますか？脳が破裂するまで永遠に？もちろんそうではありません。タスクを完了したと思うときはいつでも、特定のポイントで停止します。
あなたは人間であり、自分で推測できるので、「ネットで再帰についてもっと調べてください」と尋ねるときに、これを指定する必要はありません。
コンピューターはジャックを推測できないため、次のような明示的な末尾を含める必要があります。
また、「再帰」については Google の結果ページから開始する必要があると推測しましたが、これもコンピュータにはできないことです。再帰タスクの完全な説明には、明示的な開始点も含める必要があります。
"再帰について理解できるまで、またはwww.google.com/search?q=recursion から始めて最大 10 ページを読むまで、ネットで再帰について調べてください"
全体を把握するには、次のいずれかの本を試すことをお勧めします。
- Common Lisp: シンボリック計算への穏やかな紹介。これは、再帰の最もかわいい非数学的な説明です。
- 小さな計画者。
于 2009-04-04T21:05:36.173 に答える
26
再帰を理解するには、シャンプー ボトルのラベルを見るだけです。
function repeat()
{
rinse();
lather();
repeat();
}
これに関する問題は、終了条件がなく、再帰が無期限に繰り返されるか、シャンプーまたはお湯がなくなるまで繰り返されることです (スタックを吹き飛ばすのと同様の外部終了条件)。
于 2009-04-04T21:18:31.413 に答える
12
再帰を簡単な言葉でうまく説明している本が欲しいなら、Gödel, Escher, Bach: An Eternal Golden Braid by Douglas Hofstadter の第 5 章を見てください。コンピュータ サイエンスと数学の複雑な概念の数々を、理解できる方法で、ある説明が別の説明に基づいて説明されています。この種の概念にこれまであまり触れたことがない場合は、かなり衝撃的な本になる可能性があります。
于 2009-04-04T20:45:23.320 に答える
9
これは質問というより苦情です。再帰についてもっと具体的な質問がありますか? 掛け算と同じように、それについてはあまり書かれていません。
掛け算といえば、これを思い浮かべてください。
質問：
a*bって何？
答え：
b が 1 の場合、それは a です。それ以外の場合は、a+a*(b-1) です。
a*(b-1)とは？それを解決する方法については、上記の質問を参照してください。
于 2009-04-04T20:19:53.583 に答える
9
この非常に単純な方法は、再帰を理解するのに役立つと思います。このメソッドは、特定の条件が true になるまで自分自身を呼び出してから、次の値を返します。
function writeNumbers( aNumber ){
write(aNumber);
if( aNumber > 0 ){
writeNumbers( aNumber - 1 );
}
else{
return;
}
}
この関数は、フィードする最初の数値から 0 までのすべての数値を出力します。
writeNumbers( 10 );
//This wil write: 10 9 8 7 6 5 4 3 2 1 0
//and then stop because aNumber is no longer larger then 0
基本的に何が起こるかというと、writeNumbers(10) は 10 を書き込み、次に writeNumbers(9) を呼び出します。これは 9 を書き込み、次に writeNumber(8) を呼び出します。 butt は writeNumbers(-1) を呼び出しません。
このコードは、基本的に次のものと同じです。
for(i=10; i>0; i--){
write(i);
}
次に、for ループが本質的に同じことを行う場合、再帰を使用する理由を尋ねるかもしれません。for ループをネストする必要があるが、それらがネストされている深さがわからない場合は、主に再帰を使用します。たとえば、ネストされた配列から項目を出力する場合:
var nestedArray = Array('Im a string',
Array('Im a string nested in an array', 'me too!'),
'Im a string again',
Array('More nesting!',
Array('nested even more!')
),
'Im the last string');
function printArrayItems( stringOrArray ){
if(typeof stringOrArray === 'Array'){
for(i=0; i<stringOrArray.length; i++){
printArrayItems( stringOrArray[i] );
}
}
else{
write( stringOrArray );
}
}
printArrayItems( stringOrArray );
//this will write:
//'Im a string' 'Im a string nested in an array' 'me too' 'Im a string again'
//'More nesting' 'Nested even more' 'Im the last string'
この関数は、100 レベルにネストできる配列を取ることができますが、for ループを記述すると、それを 100 回ネストする必要があります。
for(i=0; i<nestedArray.length; i++){
if(typeof nestedArray[i] == 'Array'){
for(a=0; i<nestedArray[i].length; a++){
if(typeof nestedArray[i][a] == 'Array'){
for(b=0; b<nestedArray[i][a].length; b++){
//This would be enough for the nestedAaray we have now, but you would have
//to nest the for loops even more if you would nest the array another level
write( nestedArray[i][a][b] );
}//end for b
}//endif typeod nestedArray[i][a] == 'Array'
else{ write( nestedArray[i][a] ); }
}//end for a
}//endif typeod nestedArray[i] == 'Array'
else{ write( nestedArray[i] ); }
}//end for i
ご覧のとおり、再帰的な方法の方がはるかに優れています。
于 2009-04-04T21:04:21.387 に答える
9
実際には、再帰を使用して、目前の問題の複雑さを軽減します。簡単に解決できる単純な基本ケースに到達するまで、再帰を適用します。これにより、最後の再帰ステップを解決できます。そして、これにより、元の問題までの他のすべての再帰的ステップが行われます。
于 2009-04-04T21:04:37.110 に答える
7
例を挙げて説明しようと思います。
あなたは何を知っていますか！意味？そうでない場合: http://en.wikipedia.org/wiki/Factorial
3！= 1 * 2 * 3 = 6
ここにいくつかの擬似コードがあります
function factorial(n) {
if (n==0) return 1
else return (n * factorial(n-1))
}
それでは試してみましょう：
factorial(3)
nは0ですか？
いいえ！
そのため、再帰をさらに深く掘り下げます。
3 * factorial(3-1)
3-1 = 2
は 2 == 0 ですか?
いいえ！
だから私たちはもっと深く行きます！3 * 2 * 階乗 (2-1) 2-1 = 1
1 == 0 ですか?
いいえ！
だから私たちはもっと深く行きます！3 * 2 * 1 * 階乗 (1-1) 1-1 = 0
0 == 0 ですか?
はい！
些細なケースがあります
したがって、3 * 2 * 1 * 1 = 6 となります。
お役に立てば幸いです
于 2009-04-04T20:46:23.800 に答える
5
再帰
メソッド A を呼び出し、メソッド A がメソッド A を呼び出します。最終的に、これらのメソッド A の 1 つが呼び出されて終了することはありませんが、何かがそれ自体を呼び出しているため、再帰です。
ハードドライブ上のすべてのフォルダー名を出力したい再帰の例: (in c#)
public void PrintFolderNames(DirectoryInfo directory)
{
Console.WriteLine(directory.Name);
DirectoryInfo[] children = directory.GetDirectories();
foreach(var child in children)
{
PrintFolderNames(child); // See we call ourself here...
}
}
于 2009-04-04T20:22:59.270 に答える
5
再帰関数は、必要な回数だけ自分自身を呼び出す関数です。何かを複数回処理する必要がある場合に便利ですが、実際に何回必要になるかは不明です。ある意味では、再帰関数は一種のループと考えることができます。ただし、ループと同様に、プロセスが中断される条件を指定する必要があります。そうしないと、プロセスが無限になります。
于 2009-04-04T20:50:01.030 に答える
4
どの本を使っていますか？
実際に優れたアルゴリズムに関する標準的な教科書は、Cormen & Rivest です。私の経験では、再帰を非常によく教えています。
再帰は、プログラミングで把握するのが難しい部分の 1 つであり、本能が必要ですが、習得することができます。ただし、適切な説明、適切な例、適切な図が必要です。
また、一般的に 30 ページは多く、単一のプログラミング言語で 30 ページは混乱を招きます。一般的な本から一般的な再帰を理解する前に、C や Java で再帰を学ぼうとしないでください。
于 2009-04-04T20:14:05.267 に答える
4
http://javabat.comは、再帰を練習するための楽しくエキサイティングな場所です。彼らの例はかなり軽いものから始まり、大規模に機能します (そこまで行きたい場合)。注: 彼らのアプローチは、練習によって学ぶことです。これは、単純に for ループを置き換えるために作成した再帰関数です。
for ループ:
public printBar(length)
{
String holder = "";
for (int index = 0; i < length; i++)
{
holder += "*"
}
return holder;
}
これは、同じことを行うための再帰です。(上記のように使用されるように、最初のメソッドをオーバーロードしていることに注意してください)。インデックスを維持する別の方法もあります (上記の for ステートメントで行う方法と同様です)。再帰関数は、独自のインデックスを維持する必要があります。
public String printBar(int Length) // Method, to call the recursive function
{
printBar(length, 0);
}
public String printBar(int length, int index) //Overloaded recursive method
{
// To get a better idea of how this works without a for loop
// you can also replace this if/else with the for loop and
// operationally, it should do the same thing.
if (index >= length)
return "";
else
return "*" + printBar(length, index + 1); // Make recursive call
}
簡単に言うと、再帰はコードを減らす良い方法です。後者の printBar には、if ステートメントがあることに注意してください。条件に達した場合は、再帰を終了して前のメソッドに戻ります。このメソッドは前のメソッドに戻ります。printBar(8) を送信すると、******** が返されます。for ループと同じことを行う単純な関数の例が役立つことを願っています。ただし、Java Bat でこれをもっと練習できます。
于 2009-04-04T20:54:21.050 に答える
3
6歳の人に再帰を説明するには、まず5歳の人に説明してから、1年待ちます。
実際、これは有用な反例です。再帰呼び出しは、難しくはなく、より単純でなければならないからです。5歳の子供に再帰を説明するのはさらに難しく、0で再帰を停止することはできますが、0歳の子供に再帰を説明する簡単な解決策はありません。
再帰を使用して問題を解決するには、最初に同じ方法で解決できる1つ以上のより単純な問題に分割します。次に、問題がさらに再帰せずに解決できるほど単純な場合は、より高いレベルに戻ることができます。
実際、それは再帰の問題を解決する方法の再帰的定義でした。
于 2011-09-17T05:10:51.513 に答える
3
Common Lispでの簡単な再帰的な例:
MYMAP は、リスト内の各要素に関数を適用します。
1)空のリストには要素がないため、空のリストを返します - () と NIL は両方とも空のリストです。
2)関数を最初のリストに適用し、残りのリストに対して MYMAP を呼び出し (再帰呼び出し)、両方の結果を新しいリストに結合します。
(DEFUN MYMAP (FUNCTION LIST)
(IF (NULL LIST)
()
(CONS (FUNCALL FUNCTION (FIRST LIST))
(MYMAP FUNCTION (REST LIST)))))
トレースされた実行を見てみましょう。関数を入力すると、引数が出力されます。関数を終了すると、結果が出力されます。再帰呼び出しごとに、出力はレベルごとにインデントされます。
この例では、リスト内の各数値 (1 2 3 4) に対して SIN 関数を呼び出します。
Command: (mymap 'sin '(1 2 3 4))
1 Enter MYMAP SIN (1 2 3 4)
| 2 Enter MYMAP SIN (2 3 4)
| 3 Enter MYMAP SIN (3 4)
| | 4 Enter MYMAP SIN (4)
| | 5 Enter MYMAP SIN NIL
| | 5 Exit MYMAP NIL
| | 4 Exit MYMAP (-0.75680256)
| 3 Exit MYMAP (0.14112002 -0.75680256)
| 2 Exit MYMAP (0.9092975 0.14112002 -0.75680256)
1 Exit MYMAP (0.841471 0.9092975 0.14112002 -0.75680256)
これが私たちの結果です:
(0.841471 0.9092975 0.14112002 -0.75680256)
于 2009-04-04T21:43:31.353 に答える
3
子は暗黙的に再帰を使用します。たとえば、次のようになります。
ディズニーワールドへの遠征
私たちはまだそこにいますか?(いいえ)
私たちはまだそこにいますか? (すぐに)
私たちはまだそこにいますか?(もうすぐ...)
私たちはまだそこにいますか?(SHHHH)
私たちはまだそこにいますか?(!!!!!)
その時点で、子供は眠りに落ちます...
このカウントダウン関数は簡単な例です:
function countdown()
{
return (arguments[0] > 0 ?
(
console.log(arguments[0]),countdown(arguments[0] - 1)) :
"done"
);
}
countdown(10);ソフトウェア プロジェクトに適用されるホフスタッターの法則も関連します。
チョムスキーによれば、人間の言語の本質は、彼が無限の文法であると考えるものを生み出す有限の脳の能力です。これは、私たちが言うことができることに上限がないだけでなく、私たちの言語が持つ文の数に上限がないこと、特定の文のサイズに上限がないことを意味します. チョムスキーは、この人間の言語の創造性の根底にある基本的なツールは再帰であると主張しています。つまり、あるフレーズが同じタイプの別のフレーズの中で繰り返される能力です。「John's brother's house」と言うと、名詞句「brother's house」に名詞「house」があり、その名詞句は別の名詞句「John's brother's house」に含まれています。これは非常に理にかなっています。
参考文献
于 2012-08-30T23:26:04.577 に答える
2
痛い。私は昨年、ハノイの塔を理解しようとしました。TOHのトリッキーな点は、再帰の単純な例ではないことです。ネストされた再帰があり、呼び出しごとにタワーの役割も変更されます。私がそれを理解することができる唯一の方法は、私の心の目の中でリングの動きを文字通り視覚化し、再帰的な呼び出しが何であるかを言葉で表現することでした。最初に1つのリング、次に2つ、次に3つのリングから始めます。私は実際にインターネットでゲームを注文しました。それを手に入れるのに、おそらく脳を割るのに2、3日かかりました。
于 2009-04-05T00:09:24.467 に答える
2
再帰的なソリューションを扱うとき、私は常に次のことを試みます。
- 最初に基本ケースを確立します。つまり、階乗の解で n = 1 の場合です。
- 他のすべてのケースの一般的なルールを考え出すようにしてください
また、さまざまなタイプの再帰的ソリューションがあり、フラクタルやその他多くに役立つ分割統治アプローチがあります。
また、コツをつかむために、最初に簡単な問題に取り組んでいただけると助かります。いくつかの例では、階乗を解いて n 番目のフィボナッチ数を生成しています。
参考までに、Robert Sedgewick の Algorithms を強くお勧めします。
それが役立つことを願っています。幸運を。
于 2009-04-04T20:43:59.563 に答える
1
働き蜂を考えてみてください。はちみつを作ろうとします。それはその仕事をし、他の働きバチが残りの蜂蜜を作ることを期待しています。そして、ハニカムがいっぱいになると停止します。
魔法だと思ってください。あなたはあなたが実装しようとしているものと同じ名前の関数を持っています、そしてあなたがそれにサブ問題を与えるとき、それはあなたのためにそれを解決しますそしてあなたがする必要がある唯一のことはあなたの部分の解決策をそれの解決策と統合することですあなたにあげた。
たとえば、リストの長さを計算したいとします。関数magical_lengthとmagicalhelperをmagical_lengthで呼び出しましょう。最初の要素を持たないサブリストを指定すると、魔法によってサブリストの長さが指定されることがわかっています。次に、私たちが考える必要があるのは、この情報を私たちの仕事とどのように統合するかということだけです。最初の要素の長さは1で、magic_counterはサブリストn-1の長さを示します。したがって、全長は（n-1）+1->nです。
int magical_length( list )
sublist = rest_of_the_list( list )
sublist_length = magical_length( sublist ) // you can think this function as magical and given to you
return 1 + sublist_length
ただし、空のリストを指定するとどうなるかを考慮していなかったため、この回答は不完全です。私たちが持っているリストには常に少なくとも1つの要素があると思いました。したがって、空のリストが与えられ、答えが明らかに0である場合、答えはどうあるべきかを考える必要があります。したがって、この情報を関数に追加します。これは、ベース/エッジ条件と呼ばれます。
int magical_length( list )
if ( list is empty) then
return 0
else
sublist_length = magical_length( sublist ) // you can think this function as magical and given to you
return 1 + sublist_length
于 2011-09-07T09:12:35.873 に答える
1
再帰関数は、呼び出しごとに少し圧縮するスプリングのようなものです。各ステップで、少しの情報 (現在のコンテキスト) をスタックに置きます。最後のステップに到達すると、スプリングが解放され、すべての値 (コンテキスト) が一度に収集されます!
この比喩が効果的かどうかはわかりません... :-)
とにかく、少し人工的である古典的な例（非効率的で簡単に平坦化されるため最悪の例である階乗、フィボナッチ、ハノイ...）を超えて（実際のプログラミングのケースではめったに使用しません）、実際に使用されている場所を見るのは興味深いことです。
非常に一般的なケースは、ツリー (またはグラフですが、一般的にはツリーの方が一般的です) をたどることです。
たとえば、フォルダー階層: ファイルを一覧表示するには、それらを反復処理します。サブディレクトリが見つかった場合、ファイルをリストする関数は、新しいフォルダーを引数としてそれ自体を呼び出します。この新しいフォルダー (およびそのサブフォルダー!) のリストから戻ってくると、コンテキストが再開され、次のファイル (またはフォルダー) に移動します。
もう 1 つの具体的なケースは、GUI コンポーネントの階層を描画する場合です。ペインのようなコンテナーを使用して、ペインにすることもできるコンポーネントを保持したり、コンポーネントを複合したりするのが一般的です。ペイント ルーチンは、各コンポーネントのペイント関数を再帰的に呼び出します。保持しているすべてのコンポーネントのペイント関数を呼び出します。
私がとても明確かどうかはわかりませんが、過去に偶然見つけたものだったので、教材の実際の使用を示すのが好きです.
于 2009-04-04T20:55:06.120 に答える