再帰-よくあるプログラミングテクニックです

再帰とは?(what)

再帰時に広く応用されているアルゴリズム(またはプログラミング技術)であり、DFS深さ優先探索、前中後序二叉木遍歴など、多くのアルゴリズムの符号化実装が再帰に用いられる.

すべての再帰問題は、f(n)=f(n−1)+a,f(1)=b;再帰は関数呼び出し関数自体であり、関数には戻り値があり、一定の条件下で呼び出しを終了して階層的に返す.

再帰、関数呼び出し自体:再帰、関数戻り値:帰;

どうして再帰を使うのですか.(why)
利点:コード表現力が強く、簡潔である.欠点:空間の複雑度が高く、スタックオーバーフローのリスクがあり、繰り返し計算の可能性があり、関数呼び出しが多すぎると時間がかかります.
どのような問題が再帰的に使われますか.(when)

一つの問題の解はいくつかのサブ問題の解に分解することができる.例えばf(n)=f(n-1)+f(n-2);

この問題は分解されたサブ問題と、データの規模が異なる以外、解の構想は完全に同じである.例えばf(n)=f(n-1)+f(n-2);n,n−1,n−2はデータが異なるだけで解法関数はf

である.

は再帰的終了条件がある.例えばf(1)=1;

再帰コードの作成方法
理解する
繰返し式を書き出し、終了条件を見つけます
再帰は実は1つの方程式です:f(n)=f(n-1)+a;つまり、再帰的に設計する際には、次の3つの側面を考慮する必要があります.

f(n)を解くとき,f(n−1)が既に解けていると仮定する.f(n−1)がどのように解けるかは考えないでください.

キーは、再帰的な終了条件を見つけることです.

再帰は往々にして分治法と切り離せない.複雑な再帰の場合、再帰は分割され、マージされることが多い.

ステップ
再帰的な方法を書きます.

まず再帰終了時の操作を判断する.

再書き込み再帰分解操作;

くり
ハノタ問題は典型的な再帰思想を使うことだ.まず最も簡単なf(2)を導き、それによってf(n)を押す解は以下に分けることができる.

n-1ディスクをfrom->buffer

から

from->to

から1つのディスクを

n-1ディスクをbuffer->to

から

以上の3ステップはf(n)を解くためであり,最後に再帰終了の条件を与える.ディスクが1つしかない場合は、1回の移動操作でfrom->toが可能です.

/**
     *      
     */
    public static void move(int n,String from,String buffer,String to){
        if(n==1){
            System.out.println(from+"—>"+to);
            //   return
            return;
        }
        move(n-1,from,to,buffer);
        move(1,from,buffer,to);
        move(n-1,buffer,from,to);
    }

映画館は座席の何列目の質問をして、f(n)=f(n-1)+1、f(1)=1、

	/**
     *          
     * @param n     
     * @return
     */
    public static int ask(int n){
        if(n==1){
            return 1;
        }
        return ask(n-1)+1;
    }

注意点
1.スタックオーバーフローの警戒:
再帰用はシステムスタックまたは仮想マシン関数呼び出しスタックであり、スタック空間は一般的に大きくなく、再帰解のデータ規模が大きく、呼び出し階層が深く、スタックに押し込まれ続けると、スタックオーバーフローのリスクがある.スタックオーバーフローを回避するために、グローバル変数を宣言して再帰的な深さを制御できます.
2.繰り返し計算を警戒する:
例えば、f(n)=f(n-1)+f(n-2)、f(5)=(f 4)+f(3)、f(4)=f(3)+f(2)であり、ここでf(3)繰返し計算は、ハッシュテーブルによって既に解いた値を保存し、繰返し計算を回避する.
ランプを消す

再帰には、関数呼び出し関数自体が必要である.

再帰にはreturnが必要です.

再帰コードを書く鍵は、大きな問題を小さな問題に分解する方法の法則を見つけ、これに基づいて再帰式を書き、終了条件を推敲し、最後に再帰式と終了条件をコードに翻訳することである.

再帰コードを記述する鍵は、再帰に遭遇すれば、再帰の各ステップを人間の脳で分解しようとしないで、再帰式に抽象化することです.