C言語の再帰とは何ですか?古典的な再帰関数の例の共有

C言語の再帰とは何ですか?次の記事では、古典的な再帰関数の例を通して C 言語の再帰を理解するのに役立ちます。

再帰は、定義または説明内で直接または間接的に自分自身を呼び出す方法です。再帰関数は、自分自身を直接または間接的に呼び出す方法です。独自の関数とは、独自のプロセスを呼び出すことを意味します。

再帰を初めて使用する学生は、再帰を理解するのが難しいかもしれません。次のような理解するのが難しい点がたくさんあるかもしれません。自分自身の中で呼び出されますか? 自分自身はどうですか?

• 自分自身を呼び出すことができるので、再帰操作中に多くのレイヤーが互いにネストされているはずです。それらはいつネストされなくなりますか?

• 再帰操作中、ネストされた複数のレイヤー間でパラメーターが渡されます。複数のレイヤーは相互に影響を及ぼしますか?

• 再帰の 2 つの要素

再帰境界

• 再帰の論理 - 再帰」の式"

• 再帰的プロセスにはパラメーターの変更が必要であり、パラメーターの変更は再帰境界に関連しています。

さらに難しい質問では、これら 2 つの問題を解決するのは簡単ではありません。

再帰の諸問題について、理解している生徒は一文でわかりやすく説明できるかもしれませんが、理解していない生徒はいくら言っても理解できません。 .

以下は、再帰を [体験] するためのいくつかの簡単な例です。まず、[知覚] の観点から再帰を理解してください。

1.フィボナッチ数

フィボナッチ数の再帰に到達します。式は次のとおりです: F(0)=F(1)=1,F(n)=F(n-1) F(n-2) n>=2;これは明らかに、境界 n=0 または 1 の場合の再帰 F(n) の値と、再帰ロジック F(n)=F(n-1) F(n-2) を示します。再帰式です。したがって、この再帰関数を書くのは難しくありません

#includeusing namespace std;
int F(int n)//函数返回一个数对应的Fibonacci数{ if(n0 || n1)//递归边界
return 1; return F(n-1) + F(n-2);//递归公式}
int main(){ //测试
int n; while(cin >> n) cout << F(n) << endl;
return 0;
}

##2. 階乗の再帰式: n*F(n-1)

#コードは次のとおりです:

#includeusing namespace std;
int F(int n){ if(n==0)//递归边界
return 1;
return n*F(n-1);//递归公式}
int main(){ int n; cin >> n; cout << F(n) << endl;
return 0;
}

3. 配列の合計

配列 a[]:a[0],a[1],... が与えられたとします。 ,a[n-1]、再帰的に合計するにはどうすればよいですか?

まだ 2 つの質問があります:再帰境界と再帰公式です。再帰境界とは何ですか?現時点では簡単に考えることはできませんが、合計を考えます。複数の数値を合計するプロセスは何ですか? x、y、z、w を手動で合計するプロセスは何ですか?手順は次のとおりです。

x y=a、タスクは a、z、w 合計

a z=b、タスクは b、w 合計

b w= になります。 c 答えを得る

考えてみてください。[答えを得る] なぜこのステップで答えが得られるのでしょうか? (ナンセンス?) 数字を加えなくても答えが得られるからです。

だから、再帰の境界は、数字が 1 つしかないということです。

だから、再帰の境界では、では、再帰式の毛織物はどうでしょうか？実際、再帰式は手動計算プロセスに暗黙的に含まれています:

ここで、 は 2 つの数値の合計であり、F は複数の数値の合計を求める再帰関数です。コードは次のとおりです:

#includeusing namespace std;
int F(int a[],int start,int end){ if(start==end)//递归边界
return a[start];
return a[start] + F(a,start+1,end);//递归公式}
int main(){ int a[] = {1,2,3,4,5}; int s=0,e=4; cout << F(a,s,e) << endl;
return 0;
}

4. 配列要素の最大値を見つける

手動で最大値を見つけるプロセスは何ですか?走査して比較します。プロセスは次のとおりです:

例: 3、2、6、7、2 と 4 の最大値を見つける: 最初に最大値 max=-999999 を設定し、次に max 要素と配列要素を 1 つずつ比較します (トラバース)。 [i]>max の場合、max の値を a[i] に更新します。それ以外の場合、max は変更されず、トラバーサルが終了するまで後方へのトラバースを続けます。max

max>2、max=3 は変更されません

max

max

max> 2、max=7 は変更されません

max>4、max=7 は変更されません

トラバーサルが終了し、max=7 が最大値です。

合計と同様に、再帰式は次のとおりです:

ここで、max は 2 つの数値の大きい値の関数 F です。複数の数値の最大値を見つける再帰関数です。コードは次のとおりです:

#includeusing namespace std;
#define max(a,b) (a>b?a:b)
int F(int a[],int s,int e){ if(s==e) return a[s]; else if(s+1 == e)//递归边界
return max(a[s],a[e]);
return max(a[s],F(a,s+1,e));//递归公式!!!}
int main(){ int a[] = {5,1,4,6,2}; int s = 0,e = 4; cout << F(a,s,e) << endl;
return 0;
}

上記の例が[単純な例]である理由は、上記の再帰がすべて[一方向再帰]に属するためです。一方向再帰、再帰パスは一方向であるため、アイデアは比較的簡単に考えられます。

難しい再帰問題は、一般に一方向再帰ではなく、[バックトラッキング] メソッド、再帰の使用が必要です。このメソッドを考えるのは簡単ではありません。

以上がC言語の再帰とは何ですか?古典的な再帰関数の例の共有の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。