どうして再帰を使うの?

どうして再帰を使うの?
プログラミングの中で最も頭がつかめない基本アルゴリズムは再帰だと推定されています.多くの場合、複雑な再帰が少し時間がかかることがわかります.特にモデルに記述されている問題の概念がはっきりしていない場合、自分で再帰を設計するのはもっと難しいです.
多くの再帰を理解していない人(今日csdnの中で初心者の伝言を見ました)は、再帰はまったく必要ないと思って、循環で実現することができますが、実はこれは浅い理解です.再帰がプログラムの中で風靡できるのは彼の循環のためではないので、みんなは再帰が2歩に分かれていることを知っていて、再帰は空間の性能にとって、まるで罪を作っていることを知っていて、これは時空の完璧な人にとって、まったく受け入れることができなくて、もし再帰がただ循環であれば、今私たちは再帰が見えないと思います.再帰が現在も存在するのは、再帰が無限循環体を生成することができ、すなわち100層または10000層for循環を生成する可能性があるからである.たとえば、文字列をフルに並べ替えると、文字列の長さが不定になります.ループで実現すると、書き出せないことがわかります.このときは再帰を呼び出します.また、再帰モデルでは、forループと再帰ネストなどのブランチ再帰を使用することもできます.あるいは、このセクションでは、いくつかの再帰ステップ式を列挙して、それぞれ再帰を形成します.
帰納法で再帰を理解する
数学も悪くない私たちの第一反応は、数学に再帰されたモデルが何なのかということです.結局,我々は問題を数学的にモデリングするのがコードモデリングよりずっと得意である.(もちろん、問題がはっきりしている人は直接履歴書をモデルに戻すこともできますが、デジタルモデルを用いて仲介しているのは、まだはっきりしていない人向けです)
自分で再帰を観察すると、再帰の数学モデルは実は帰納法であり、これは高校の数列の中で最もよく使われていることがわかります.帰納法を思い出す.
帰納法は,一つの問題を解決して彼のサブ問題を解決しようとするのに適しており,彼のサブ問題はまたサブ問題のサブ問題になり,これらの問題は実際にはモデルであり,つまり同じ論理帰納処理項があることを発見した.もちろん例外があります.つまり、再帰終了のどの処理方法が私たちの帰納処理項目に適用されないか、もちろん適用できません.そうしないと、私たちは無限再帰します.ここではまた,帰納終点と直接解く式を導いた.リストを用いて帰納法を形容すると、
ステップ式:問題がサブ問題に脱皮する式終了条件:ステップ式ではなくいつでも使用できます.
直接解式:終了条件で戻り値を直接計算できる式論理帰納項:終了条件に適用されないすべてのサブ問題の処理に適用され、もちろん上のステップ式は実はここに含まれています.
これで実は終わり、再帰も出てきました.再帰アルゴリズムの一般的な形式:

void func( mode)
{
    if(endCondition)
    {
        constExpression         //   
    }
    else
    {
        accumrateExpreesion     //   
        mode=expression         //     
            func(mode)          //    ，  
    }
}

最も典型的なのはNです!アルゴリズム、これは最も説得力があります.再帰的な考え方や使用シーンを理解することで、基本的に自分で設計することができます.もちろん、他のアルゴリズムと組み合わせて使用するには、実践と総括が必要です.

#include "stdio.h"
#include "math.h"

int main(void)
{
    int n, rs;

    printf("           n：");
    scanf("%d",&n);

    rs = factorial(n);
    printf("%d ", rs);
}

//       
int factorial(n){
     if(n == 1) {
          return 1;
     }
     return n * factorial(n-1);
}

階乗の再帰を求めるのは簡単で、ここでは展開しません.
再帰的な例を2つ追加します
ツリーの深さを返します.

int depth(Tree t){
      if(!t) return 0; 
    else { 
        int a=depth(t.right); 
        int b=depth(t.left); 
        return (a>b)?(a+1):(b+1); 
    } 
}

ツリーがバランスしているかどうかを判断します.

int isB(Tree t){
      if(!t) return 0; 
    int left=isB(t.left); 
    int right=isB(t.right); 
    if( left >=0 && right >=0 && left - right <= 1 || left -right >=-1) 
        return (left < right)? (right +1) : (left + 1); 
    else return -1; 
} 

1つ目のアルゴリズムは理解しやすいが、2つ目はそれほど理解しにくい.最初のアルゴリズムの考えは、この木が空であれば0を返すことです.そうでなければ、まず左の木の深さを求め、右の数の深さを求め、この2つの値を比較してどの値が大きいかを+1にします.2番目のアルゴリズムは、まずisB関数の機能を理解しなければならない.それは空のツリーに対して0を返し、バランスツリーに対してツリーの深さを返し、アンバランスツリーに対して-1を返す.関数の機能が分かってからコードを見ればずっと分かりますが、1つの関数が-1を返すと、関数全体が-1を返します.(具体的な過程はよく見ればわかる)
再帰的には,関数の機能的意義の面から理解することが望ましい.問題がどのようにそのサブ問題に分解されるかを理解することで,再帰関数コードについても理解できる.ここには(私も深く陥ったことがある)エラーがあります.スタックを分析し、関数の呼び出しプロセスを分析し、結果を出力して再帰的なアルゴリズムを分析します.これはとてもいけないので、このように自分を酔わせるだけで、実は再帰は本質的に関数の呼び出しで、呼び出す関数は自分であるか、自分ではないかは実は何の違いもありません.関数呼び出し時にスタックに一時的な情報が保存されます.スタックは関数が正しく戻るためだけです.それだけです.再帰が大量の関数呼び出しをもたらし,大量のスタック操作をもたらすことを知ればよい.
小結
再帰の基本思想は規模の大きい問題を規模の小さい類似のサブ問題に転化して解決することである.関数実装では,大きな問題を解決する方法と小さな問題を解決する方法が同じ方法であることが多いため,関数呼び出し自体が生じる.また,この問題を解決する関数には明らかな終了条件が必要であり,無限再帰は生じない.
拡張読書
この記事のトピックのリストは次のとおりです.
漫談再帰:再帰の思想漫談再帰:再帰が満たす必要がある2つの条件漫談再帰:文字列回文現象の再帰判断漫談再帰:二分ルックアップアルゴリズムの再帰実装漫談再帰:再帰の効率問題漫談再帰:再帰とサイクル漫談再帰:ループと反復は同じことですか?
再帰計算プロセスと反復計算プロセス漫談再帰:フィボナッチから尾再帰を理解する
漫談再帰:末尾再帰とCPS 漫談再帰:いくつかのContinuationの知識を補充する漫談再帰:PHPの末尾再帰とその最適化漫談再帰:アセンブリから見た末尾再帰の最適化転載先:http://www.nowamagic.net/librarys/veda/detail/2314