再帰アルゴリズム効率の概要

前の文章では再帰アルゴリズムについて述べ,いくつかの基礎的な紹介を行い,いくつかの比較的簡単な例を挙げた.今日も再帰問題なので、皆さんに分かち合いましょう.
再帰で最もよく発生する問題はスタックオーバーフローであるため,関数再帰には適切な終了条件が必要である.関数は、再帰するたびに新しい呼び出しが行われるたびに、再帰関数の前の呼び出しで作成された変数を隠す変数を作成します.
前節で述べた再帰関数による階乗の実現については,実際には階乗の良い例ではなく,このやり方が「高級」であると考える人が多いが,実際にはそうではない,このやり方の効率は循環で階乗を求めるのに何の優位性もなく,逆に階乗で行うと恐怖の効率の低さをもたらす問題がある.階乗は関数の1回1回の呼び出しであり、各関数のオン、パラメータはスタックに押し込まなければならない、局所変数にメモリ空間を割り当てなければならない、レジスタの値は保存しなければならないなど、すべての再帰はこのようにしているので、簡単な循環反復で解決できることは、メモリ消費を大きくする必要はありませんか?
もしあなたが疑っているなら、階乗でフィボナッチ数を求めてみてください.フィボナッチ数は階乗の形で定義されていますが、階乗で求めるのはどうですか.次のコードを実行して、50番目のフィボナッチ数を計算して、次の再帰アルゴリズムで結果がどのくらいかかるかを計算してみてください--

#include
int fibonacci(int n);
int main()
{
	int n = 0;
	printf("please enter a figer>
");
	scanf("%d", &n);
	printf("%d",fibonacci(n));
	return 0;
}
int fibonacci(int n)
{
	if (n <= 2)
	return 1;
	else
	return fibonacci(n-1) + fibonacci(n-2);
}

目測で少なくとも10分はかかると思いますが.......この効率は、想像できないでしょう.だから、再帰するだけでなく、いつ使うべきか、いつ使うべきかを知る必要があります.簡単に分析してみると、なぜ上から再帰で少し大きなフィボナッチ数を求めるのがこのように非効率なのか、関数では、フィボナッチ数の計算ごとに前の数と前の数に分割されているのか、このように推すと、2のn次方の恐怖を聞いたことがあるかどうか分からないので、30番目のフィボナッチ数を計算するとき、3番目のフィボナッチ数は317811回計算されます......、50番目のフィボナッチ数を計算すると、あなたのパソコンが狂って動いていることが想像できますが、まだ結果が出ません!!したがって、フィボナッチ数の計算は反復的な方法で計算され、コードは以下の通りである.

#include
int main()
{
	int x = 0;
	printf("        n      :
");
	scanf("%d",&x);
	long next = 1;
	long previous = 1;
	long result = 1;
	while (x > 2)
	{
		x--;
		previous = next;
		next = result;
		result = next + previous;
	}
	printf("      ：%ld
", result);
	return 0;
}