再帰——線形再帰と二分再帰

再帰
リニア再帰
例1:配列加算

int sum( int A[], int n) {		//      ：     
	if ( 1 > n )		//    ，   
		return 0;		//    
	else				//    
		return sum(A, n-1) + A[n - 1];		//  ： n-1   ，    n-1 
}

各再帰インスタンスは、自身に対して複数回呼び出されます.したがって、各階層には1つのインスタンスしかなく、線形の順序関係を構成します.このような再帰モードは「線形再帰」と呼ばれ、再帰の最も基本的な形式である.
再帰アルゴリズムは、再帰ベースを設定し、常に実行されることを確認する必要があります.各クラスで発生する可能性のある平凡な状況に対して、対応する再帰ベースを設定する必要があります.再帰基は1つだけではないかもしれません.
例2:配列逆転
配列反転アルゴリズムの統合エントリ:

void reverse(int*, int, int);       //         

void reverse(int* A, int n)        //    
{ reverse(A, 0, n-1); }            //               

void reverse(int* A, int lo, int hi) {  //    (     )
    if（lo < hi) {
        swap( A[li], A[hi] );           //  
        reverse(A, lo+1, hi-1 );        //    A(lo,hi)
    } //else        
}

テール再帰とその除去
オンライン再帰アルゴリズムでは、再帰呼び出しが再帰インスタンスで最後の操作として適切に現れる場合、テール再帰と呼ばれる.上記の配列逆転アルゴリズムは典型的なテール再帰である.
最後の再帰形式のアルゴリズムで、等価な反復バージョンに変換できます.

void reverse(int* A, int lo, int hi) {  //    (   )
next:   //            
    if (lo < hi) {
        swap( A[lo], A[hi] );       //  
        lo ++; hi-- ;               //       
        goto next;                  //       
    }  //else        
}

goto文はできるだけ回避したほうがいいので、さらに調整してgoto文を消去します

void reverse( int* A, int lo, int hi) {
    while(lo < hi)
        swap(A[lo++], A[hi--]);
}

二分再帰
各再帰インスタンスは、複数回再帰することができるので、「多重再帰」と呼ばれます.通常、元の問題を2つに分けるので、「二分再帰」と呼ばれます.
例1:配列加算(二分再帰版)

int sum(int A[], int lo, int hi) {  //      ：     
    if (lo == hi)  
        return A[lo];       //    
    else {
        int mi = (lo + hi) >> 1;        //       ，        
        return sum(A,lo,mi) + sum(A,mi+1,hi);       //         ，    
    }
}

例2:Fibonacci数:二分再帰
Fibonacci数列第n項fib(n)の計算問題を調べ、この数列の定義は以下の通りである.
fib(n) = n;                            n <= 1
fib(n) = fib(n-1) + fib(n-2);    n>= 2
2点再帰版:

_int64 fib( int n ) { //  Fibonacci    n 
    return ( 2 > n ) ? 
        (_int64) n      //      ，    
        : fib(n - 1) + fib(n - 2);      //  ，       ，      

このアルゴリズムは簡潔であるが,効率とその低下,これは指数的複雑度アルゴリズムであり,時間的複雑度はO(2^n)である.
最適化ポリシー:
一定量の補助空間を借りて,各サブ問題を解いた後,対応する解答をタイムリーに記録した.
1.タブまたはメモリポリシー
線形再帰版:

_int64 fib(int n, _int64& prev) {   //  Fibonacci   n :    fib(n,prev)
    if ( n == 0)                    //      
    { prev = 1; return 0; }         //    :fib(-1) = 1, fib(0) = 0
    else {
        _int64 prevPrev; prev = fib(n-1,prevPrev);      //       
        return prevPrev + prev;     //      
    }
}//          ，        ，      O(n)

2.動的計画戦略
上記の線形再帰版fib()アルゴリズムでは、記録された各サブ問題の解答は、1回しか使用されず、このアルゴリズムが再帰ベースに到達した後の層毎の戻り過程で、上へ1層戻るたびに、以下の各層の解答が保持される必要はないことがわかる.
反復版:

_int64 fibI( int n ) {  //  Fibonacci    n (   ):O(n)
    _int64 f = 1, g = 0;        //   ：fib(-1),fib(0)
    while(n-- > 0)  { g += f; f = g - f; }      //      ，  n        fib(n)
    return g;
}

ここでは2つの中間変数fとgのみを用いて,現在の一対の隣接するFibonacci数を記録した.アルゴリズム全体は線形ステップの反復のみを必要とし,時間複雑度はO(n)であった.