アルゴリズムノート-再帰

3行のコードで最終推薦者を見つける方法
本文の創作のインスピレーションは極客時間王争先生の「データ構造とアルゴリズムの美」課程に由来し、授業後の反省と各位の学友の発言の総括を参考にして、現在自分の知識の構造を整理して、後日温故知新して、欠陥を調査して補う.
何だ?
再帰とは

再帰は非常に効率的で簡潔な符号化技術であり、非常に広く応用されているアルゴリズムである.自身を呼び出すことで問題を解決し,呼び出すことを渡し,返すことを帰と呼ぶ.

どうして
再帰を使用する理由

再帰は実は問題を解決する思想の具現化である.ある問題を多数のサブ問題に分けるが,サブ問題を解決する考え方と現在の問題を解決する考え方は同じである.

再帰コードは簡潔で、表現力が強い.

どうしよう
どのように学習して再帰します

まず、どのような問題が再帰的に解決するのに適しているかを理解する.

1:1つの問題はいくつかのサブ問題に分けて解くことができる.2:この問題はその後に分解されたサブ問題とデータ規模が異なる以外は,解題の考え方は同じである.3:終了条件が再帰的に存在します.

再帰コードの作成方法

は、現在の問題を解決することと、現在の分体が分解したサブ問題を解決することとを、同じ式で解くことができる繰返し式を導く.

は、大きな問題を小さな問題に分解することは、小さな問題がよりよく解決されることにあるという終了条件を決定する.では,再帰的に分解された問題は,最小の問題,すなわち再帰的に渡される終了条件でなければならない.

は、繰返し式をコードに変換する.

再帰コードを非再帰コードに変更する方法

再帰コード1:シーン計算あなたは映画館の何列目で、あなたの前にn人がいて、1人目は3列目です.

    public int fn(int n){
     
        if(n == 1){
     
            return 3;
        }else{
     
            return fn(n - 1) + 1;
        }
    }
    //     
    public int notFn(int n){
     
        int sum = 3;
        for(int i = 1;i <= n; i++){
     
            sum += 1;
        }
        return sum;
    }

まず,fn(n)=fn(n−1)+1のうちfn(1)=3の繰返し式を導出した.上記の再帰コードでは、nは私たちの前に何人いるかを表しています.もし私たちが自分が現在何列目なのかを知りたいなら、前の人が何列目なのかを知ってから、1つを加えると私たちの列数になります.従って、fn(n)=fn(n−1)+1の繰返し式に進む.再帰を使用するには終了条件が必要です.私たちの終了条件は、最初の人が3番目の列に並び、列数が決定されます.すなわち、fn(1)=3です.非再帰コードは、上述した非再帰コードのような反復サイクルを用いて実現される.

再帰コード2:シーン計算屋上に登る方法はいくつかあります.毎回階段を1つか2つしか上がらない

です.

    //    
    public int fn(int n){
     
        if(n == 1){
     
            return 1;
        }
        if(n == 2){
     
            return 2;
        }
        return fn(n - 1) + fn(n - 2);
    }
    //     
    public int notFn(int n){
     
        int sum = 0;
        int prepre = 1;
        int pre = 2;
        for(int i = 3;i <= n; i++){
     
            sum = prepre + pre;
            pre = sum;
            prepre = pre;
        }
        return sum;
    }

上記の例:階段を上るには、第一歩を踏み出すには2つの選択肢があります.1段目と2段目、2段目のときと同じように2つの選択肢があるので、毎回階段数を減らして2段目を減らす方法を求めています.繰返しの推定式は、fn(n)=fn(n−1)+fn(n−2);終了条件は,n＝1のときfn(1)＝1,n＝2のときfn(2)＝2である.非再帰コードの実現は,循環体におけるコードprepreの値がfn(n−2)を表し,preの値がfn(n−1)を表すことが最も理解しにくい.では,循環体内ではまずfn(n)すなわちpre+preを求める.次にpreが現在のfn(n)に等しい値を変更し、preが現在のfn(n−1)に等しい値を変更すると、次の循環体は、fn(n+1)=fn(n)+fn(n−1)であり、現在のpre+preである.
注意事項

再帰コードはスタックオーバーフローを警戒しなければならない.再帰メソッドは,自身を呼び出すたびにメモリスタックに関数の一時変数を格納し,再帰レベルが高く深さが大きいとスタックオーバーフローのリスクがあり,システムがクラッシュする.再帰呼び出しの深さを制限し、スタックオーバーフローを回避できます.ただし、再帰的に呼び出す最大深さは、現在のスレッドスタックの残りの空間によって決定されるため、リアルタイム計算が複雑すぎる場合は、事前に適切な深さを計算することはできません.もちろん、50未満などの再帰深さが小さい場合、スタックオーバーフローを回避するために、再帰深さを制限する方法を採用することができる.

再帰コードは、ループ計算を警戒しなければならない.現在の問題を複数のサブ問題に分解し,サブ問題をサブ問題に分解すると,問題分解の過程で必ず同じサブ問題が現れる.では,計算解の過程で,同じサブ問題を何度も解いたことがあるが,これはシステム資源を浪費している.この場合,キー値対オブジェクト,サブ問題をキー値,サブ問題の解を値として構築し,格納することができる.サブ問題を解く場合は、キー値対オブジェクトから現在のサブ問題があるかどうかを検索し、ある場合は直接値を計算しません.ボールが後で格納されている場合は、次回アクセスするために保存します.

効率の問題:再帰コードが複数回呼び出されると、かなりの時間コストが発生します.再帰的な呼び出しのたびに、メモリスタックにフィールドデータを保存し、スペースオーバーヘッドのコストを増大させます.

3行のコードで最終推薦者を見つける方法

    //       
    public Long getTop(Long id){
     
        Long parentId = "SELECT parentId FROM table WHERE ID = id";
        if(parentId == null) return id;
        return getTop(parentId);
    }

上記は偽のコードで、皆さんは理解できるはずです.再帰深さが深い場合、上のコードではスタックオーバーフローの予防は行われていません.推奨者関連関係に誤った指向が発生した場合、再帰無限呼び出しの検証も行われません.
まとめ
王争先生は2つの高度な総括を与えました:1:再帰コードを書く鍵はどのように大きい問題を小さい問題に転化する法則を探し出して、しかもこれに基づいて再帰式を書いて、更に再帰式の終了条件を推敲して、最後に再帰式と終了条件をコードに翻訳します.2:再帰に遭遇すれば,それを再帰式に抽象化し,再帰の各ステップを人間の脳で分解しようとする必要はない.