アルゴリズム入門——再帰

思想:直接または間接的に自身を呼び出して次の計算を行う.
一般的な実装プロセス:関数またはサブプロシージャ、直接または間接的に関数またはサブプロシージャを呼び出すことによって計算されます.
要件:
ループ呼び出しのたびに,問題を解く規模を縮小しなければならない.
隣接する2回のループ呼び出しは、密接に関連しなければならない.通常、前の呼び出し結果は後の呼び出しの入力である.
再帰サイクル終了条件である出口が必要です.
注意:再帰呼び出しのアルゴリズムの実行効率は通常低く、呼び出し回数が多すぎるとスタックがオーバーフローする可能性があります.
例:階乗を求める

#include
int fact(int n);
void main(){
 int i;
 printf("input:");
 scanf("%d",&i);
 printf("%d      :%d",i,fact(i));
 getch();
}

int fact(int n){
 if(n<=1)
  return 1;
 else
  return fact(n-1)*n;
}

分析:再帰的なアルゴリズムの思想は実は難しくなくて、簡単に言えば:繰り返しの呼び出し自身が問題を解くことです.しかし,再帰を選択するタイミングは重要であり,複雑な問題があり,再帰で簡単に解決できる.これはあなたの注意深い分析が必要です.
プロセスの実行:
プログラムが実行されると
printf("%dの乗算結果:%d",i,fact(i))の場合、関数fact(i)の呼び出しが開始されます.関数fact()では、n=i;nが1以下であるか否かを判断し(これは重要であり、再帰終了の条件である)、小さい場合は1を返し、そうでない場合はfact(n−1)*n、すなわちもう一度呼び出す関数fact()を返し、関数のパラメータは1未満であり、これが満たすたびに、問題規模は縮小された再帰原則が必要である.もう一度呼び出した後、判断し、次に呼び出し、nが1以下になるまで判断する.このとき,数回の再帰呼び出しにより,結果が出るまで関数の戻り値はますます大きくなる.