再帰(コンピューターサイエンス)

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

Logoプログラミング言語を使用して作成され、再帰に大きく依存しているツリー各ブランチは、ツリーの小さいバージョンと見なすことができます。

コンピュータサイエンス再帰は解決策は、同じ問題の少ないインスタンスへのソリューションに依存して、問題を解決する方法です。[1]このような問題は通常、反復によって解決できますが、プログラミング時に小さなインスタンスを識別してインデックスを作成する必要があります。再帰は、独自のコード内から自分自身を呼び出す関数使用することにより、このような再帰的な問題を解決します。このアプローチは多くの種類の問題に適用でき、再帰はコンピュータサイエンスの中心的な考え方の1つです。[2]

再帰の力は、明らかに、有限のステートメントによってオブジェクトの無限のセットを定義する可能性にあります。同様に、このプログラムに明示的な繰り返しが含まれていない場合でも、有限の再帰プログラムによって無限の数の計算を記述することができます。

—  Niklaus Wirthアルゴリズム+データ構造=プログラム、1976 [3]

ほとんどのコンピュータープログラミング言語は、関数が独自のコード内からそれ自体を呼び出すことを許可することにより、再帰をサポートしています。一部の関数型プログラミング言語(Clojureなど[4]は、ループ構造を定義せず、再帰のみに依存してコードを繰り返し呼び出します。これらの再帰のみの言語はチューリング完全であることが計算可能性理論証明されています。これは、などの制御構造に基づく命令型言語同じくらい強力である(同じ問題を解決するために使用できる)ことを意味します。 whilefor

関数をそれ自体の内部から繰り返し呼び出すと、呼び出しスタックのサイズが、関連するすべての呼び出しの入力サイズの合計に等しくなる可能性があります。したがって、反復によって簡単に解決できる問題の場合、再帰は一般に効率が低く、大きな問題の場合は、末尾呼び出しの最適化などの最適化手法を使用することが基本です。[要出典]

再帰関数とアルゴリズム

一般的なコンピュータープログラミングの戦術は、問題を元の問題と同じタイプのサブ問題に分割し、それらのサブ問題を解決して、結果を結合することです。これは、分割統治法と呼ばれることがよくあります。以前に解決されたサブ問題の結果を格納するルックアップテーブル組み合わせると(繰り返し解決して余分な計算時間を発生させないようにするため)、動的計画法またはメモ化と呼ばれることがあります

ベースケース

再帰関数の定義には、関数が(繰り返しなしで)結果を自明に生成する入力を意味する1つ以上の基本ケースと、プログラムが繰り返し(自分自身を呼び出す)入力を意味する1つ以上の再帰ケースがあります。 。たとえば、階乗関数は方程式0!によって再帰的に定義できます= 1であり、すべてのn > 0の場合、n= nn − 1)!どちらの方程式もそれ自体で完全な定義を構成するわけではありません。1つ目は基本ケースで、2つ目は再帰的なケースです。ベースケースは再帰の連鎖を断ち切るため、「終了ケース」と呼ばれることもあります。

再帰的なケースの仕事は、複雑な入力をより単純な入力に分解することと見なすことができます。適切に設計された再帰関数では、再帰呼び出しごとに、最終的に基本ケースに到達する必要があるように、入力問題を単純化する必要があります。 (通常の状況で終了することを意図していない関数(一部のシステムおよびサーバープロセスなど)は、これの例外です。)ベースケースの記述を怠ったり、誤ってテストしたりすると、無限ループが発生する可能性があります

一部の関数(e = 1/0!+ 1/1!+ 1/2!+ 1/3!+ ...級数計算する関数など)の場合、入力データによって示される明確な基本ケースはありません。 ; これらの場合、基本ケースを確立する「停止基準」を提供するためにパラメーター追加する用語の数など)を追加できますそのような例は、コアカーションによってより自然に扱われます[どのように?]ここで、出力の連続する項は部分和です。これは、インデックスパラメータを使用して「n番目の項(n番目の部分和)を計算する」と言うことで再帰に変換できます

再帰データ型

多くのコンピュータプログラムは、任意の量のデータを処理または生成する必要があります再帰は、正確なサイズがプログラマーに知られていないデータを表すための手法です。プログラマーは、自己参照定義を使用してこのデータを指定できます自己参照定義には、帰納的定義誘導的定義の2つのタイプがあります。

帰納的に定義されたデータ

帰納的に定義された再帰的データ定義は、データのインスタンスを構築する方法を指定するものです。たとえば、リンクリストは帰納的に定義できます(ここでは、Haskell構文を使用)。

データ ListOfStrings  =  EmptyList  |  短所 文字列 ListOfStrings

上記のコードは、文字列のリストを空にするか、文字列と文字列のリストを含む構造体を指定しています。定義内の自己参照により、任意の(有限の)数の文字列のリストを作成できます。

帰納的定義の別の例は、自然数(または正の整数)です。

自然数は1またはn + 1のいずれかです。ここで、nは自然数です。

同様に、再帰的定義、プログラミング言語ステートメントの構造をモデル化するためによく使用されます。言語設計者は、バッカス・ナウア記法などの構文で文法を表現することがよくあります乗算と加算を使用した算術式の単純な言語の文法は次のとおりです。

 < expr >  :: =  <数値> 
          | < expr > * < expr >
          | < expr > + < expr >

これは、式が数値、2つの式の積、または2つの式の合計のいずれかであることを示しています。2行目と3行目の式を再帰的に参照することにより、文法では(5 * ((3 * 6) + 8))、1つの式に複数の積または合計演算を含む、などの任意に複雑な算術式を使用できます。

共誘導的に定義されたデータとコアカーション

共誘導データ定義は、データの一部に対して実行される可能性のある操作を指定するものです。通常、自己参照の共誘導定義は、無限のサイズのデータ​​構造に使用されます。

非公式に与えられた文字列の無限ストリームの共同定義は、次のようになります。

文字列のストリームは、次のようなオブジェクトです。
 head(s)は文字列であり、
 tail(s)は文字列のストリームです。

これは、文字列のリストの帰納的定義に非常に似ています。違いは、この定義はデータ構造のコンテンツにアクセスする方法(つまり、アクセサー関数headを介して)tailとそれらのコンテンツが何であるかを指定するのに対し、誘導定義は構造の作成方法とその作成元を指定することです。

Corecursionは共誘導に関連しており、(おそらく)無限オブジェクトの特定のインスタンスを計算するために使用できます。プログラミング手法として、これは遅延プログラミング言語のコンテキストで最も頻繁に使用され、プログラムの出力の目的のサイズまたは精度が不明な場合の再帰よりも望ましい場合があります。このような場合、プログラムには、無限に大きい(または無限に正確な)結果の定義と、その結果の有限部分を取得するためのメカニズムの両方が必要です。最初のn個の素数を計算する問題は、コアカーシブプログラム(例:ここで解決できる問題です。

再帰の種類

単一再帰と複数再帰

自己参照を1つだけ含む再帰は、次のように知られています。 単一の再帰、複数の自己参照を含む再帰は、複数の再帰単一再帰の標準的な例には、線形検索や因子関数の計算などのリストトラバーサルが含まれますが、複数再帰の標準的な例には、深さ優先探索などのツリートラバーサルが含まれます。

多くの場合、単一の再帰は複数の再帰よりもはるかに効率的であり、通常、線形時間で実行され、一定のスペースを必要とする反復計算に置き換えることができます。対照的に、複数の再帰は指数関数的な時間とスペースを必要とする場合があり、より基本的に再帰的であり、明示的なスタックなしでは反復で置き換えることができません。

複数の再帰を単一の再帰に変換できる場合があります(必要に応じて、そこから反復に変換できます)。たとえば、フィボナッチ数列の単純な計算は複数回の反復ですが、各値には2つの前の値が必要であるため、2つの連続する値をパラメーターとして渡すことにより、1回の再帰で計算できます。これは、コアカーションとしてより自然に組み立てられ、初期値から構築され、各ステップで2つの連続する値を追跡しますコアカーション:例を参照してくださいより洗練された例は、複数の再帰ではなく、反復的なツリートラバーサルを可能にするスレッド化されたバイナリツリーを使用することです。

間接再帰

再帰の最も基本的な例、およびここに示されているほとんどの例は、 関数がそれ自体を呼び出す直接再帰間接再帰は、関数がそれ自体ではなく、呼び出された別の関数によって(直接または間接的に)呼び出されたときに発生します。たとえば、 ffを呼び出す場合、それは直接再帰ですが、 ffを呼び出すgを呼び出す場合、それはfの間接再帰です3つ以上の機能のチェーンが可能です。たとえば、関数1は関数2を呼び出し、関数2は関数3を呼び出し、関数3は関数1を再度呼び出します。

間接再帰は相互再帰とも呼ばれ、より対称的な用語ですが、これは単に強調の違いであり、異なる概念ではありません。つまり、fg呼び出し、次にgfを呼び出し、次にg再びgを呼び出す場合fのみの観点からはfは間接的に再帰しますが、gのみの観点からは、間接的に再帰します。両方の観点から、fgは相互に再帰しています。同様に、相互に呼び出す3つ以上の関数のセットは、相互再帰関数のセットと呼ぶことができます。

匿名再帰

再帰は通常、名前で関数を明示的に呼び出すことによって行われます。ただし、再帰は、現在のコンテキストに基づいて関数を暗黙的に呼び出すことによっても実行できます。これは、匿名関数に特に役立ち、匿名再帰として知られています

構造的再帰と生成的再帰

一部の作成者は、再帰を「構造的」または「生成的」のいずれかに分類します。この違いは、再帰的プロシージャが処理対象のデータを取得する場所と、そのデータを処理する方法に関連しています。

[構造化データを消費する関数]は通常、引数を直接の構造コンポーネントに分解してから、それらのコンポーネントを処理します。直接のコンポーネントの1つが入力と同じクラスのデータに属している場合、関数は再帰的です。そのため、これらの関数を(構造的に)再帰関数と呼びます。

—  Felleisen、Findler、Flatt、およびKrishnaurthi、プログラムの設計方法、2001年[5]

したがって、構造的に再帰的な関数の特徴は、各再帰呼び出しの引数が元の入力のフィールドの内容であるということです。構造的再帰には、XML処理、二分木作成、検索など、ほぼすべてのツリー走査が含まれます。自然数の代数的構造(つまり、自然数がゼロまたは自然数の後継)を考慮することにより、次のような機能が得られます。因子としては、構造的再帰と見なすこともできます。

生成的再帰は代替手段です。

多くのよく知られている再帰的アルゴリズムは、指定されたデータからまったく新しいデータを生成し、それを繰り返します。 HtDPプログラムの設計方法)では、この種を生成再帰と呼びます。生成的再帰の例にはgcdクイックソート二分探索マージソートニュートン法フラクタル、および適応積分が含まれます。

—  Matthias Felleisen、高度な関数型プログラミング、2002 [6]

この区別は、関数の終了証明する上で重要です。

  • 有限(帰納法で定義された)データ構造のすべての構造的再帰関数は、構造的帰納法を介して簡単に終了することを示すことができます。直感的に、各再帰呼び出しは、基本ケースに到達するまで、より小さな入力データを受け取ります。
  • 対照的に、生成的に再帰的な関数は、必ずしも再帰的な呼び出しに小さな入力を供給するとは限らないため、それらの終了の証明は必ずしも単純ではなく、無限ループを回避するにはさらに注意が必要です。これらの生成的再帰関数は、多くの場合、コアカーシブ関数として解釈できます。各ステップで、ニュートン法の逐次近似などの新しいデータが生成されます。このコアカーションを終了するには、データが最終的に何らかの条件を満たす必要がありますが、必ずしも保証されているわけではありません。
  • ループバリアントに関して、構造的再帰とは、明らかなループバリアント、つまりサイズまたは複雑さが存在する場合であり、有限から始まり、各再帰ステップで減少します。
  • 対照的に、生成再帰は、そのような明白なループバリアントがなく、終了が必ずしもゼロに減少しない「近似誤差」などの関数に依存する場合であり、したがって、終了はさらなる分析なしでは保証されません。

実装の問題

実際の実装では、純粋な再帰関数(基本ケースの単一チェック、それ以外の場合は再帰ステップ)ではなく、明確さまたは効率を目的として、いくつかの変更を行うことができます。これらには以下が含まれます:

  • ラッパー関数(上部)
  • ベースケースの短絡、別名「アームズレングス再帰」(下部)
  • ハイブリッドアルゴリズム(下部)–データが十分に小さい場合は別のアルゴリズムに切り替えます

エレガンスに基づいて、ラッパー関数は一般的に承認されていますが、特に学界では、ベースケースの短絡は嫌われています。ハイブリッドアルゴリズムは、効率を上げるためによく使用され、小さなケースでの再帰のオーバーヘッドを削減します。アームの長さの再帰は、この特殊なケースです。

ラッパー関数

ラッパー関数は直接呼び出される代わりに、実際に再帰を行う別の補助関数を呼び出し、自分自身を再帰しない機能です。

ラッパー関数を使用して、パラメーターの検証(再帰関数がこれらをスキップできるようにする)、初期化(メモリの割り当て、変数の初期化)の実行、特に「再帰レベル」やメモ化の部分計算などの補助変数の実行、および例外とエラーの処理を行うことができます。 。ネストされた関数をサポートする言語では、補助関数をラッパー関数内にネストして、共有スコープを使用できます。ネストされた関数がない場合、補助関数は、可能であればプライベート(直接呼び出されないため)の代わりに別個の関数であり、情報は参照渡しを使用してラッパー関数と共有されます

ベースケースの短絡

階乗:通常対短絡
通常の再帰 短絡再帰
int fac1 int n {   
   if n <= 0    
      1を返します; 
   そうしないと
      戻り値fac1 n -1 * n ; 
}
static int fac2 int n {    
   // assert(n> = 2); 
if n == 2       
      2を返します; 
   そうしないと
      戻り値fac2 n -1 * n ; 
}
int fac2wrapper int n {   
   if n <= 1    
      1を返します; 
   そうしないと
      fac2 n );を返します。 
}

アームズレングス再帰も呼ばれるベースケースの短絡は、前にベースケースをチェックすることで構成されます再帰呼び出しを行う-つまり、呼び出してから基本ケースをチェックするのではなく、次の呼び出しが基本ケースになるかどうかをチェックします。短絡は、効率上の理由から特に行われ、すぐに戻る関数呼び出しのオーバーヘッドを回避します。基本ケースはすでにチェックされているため(再帰ステップの直前)、個別にチェックする必要はありませんが、全体的な再帰が基本ケースから始まる場合は、ケースのラッパー関数を使用する必要があります。自体。たとえば、階乗関数では、適切に基本ケースは0です。 = 1、すぐに1を1に返します!短絡であり、0を見逃す可能性があります。これは、ラッパー関数によって軽減できます。ボックスには、階乗のケース0と1をショートカットするCコードが表示されます

短絡は主に、ツリー内のNullポインターなど、多くの基本的なケースが発生した場合に懸念されます。これは、関数呼び出しの数を線形にすることができるため、Onアルゴリズムを大幅に節約できます。これは、深さ優先探索について以下に示されています。ツリーでの短絡は、空のノードを基本ケースと見なすのではなく、リーフ(子のない空でないノード)を基本ケースと見なすことに対応します。階乗の計算など、基本ケースが1つしかない場合、短絡はO(1)の節約になります。

概念的には、短絡は、同じベースケースと再帰ステップを持ち、再帰の前にのみベースケースをチェックするか、または異なるベースケース(標準のベースケースから1ステップ削除)と見なすことができます。ツリーのベースケースとしてヌルノードではなくリーフノードを検討する場合のように、より複雑な再帰ステップ、つまり「有効をチェックしてから再帰する」。短絡は、ベースケースの明確な分離と標準的な再帰の再帰ステップと比較して、より複雑な流れを持っているため、特に学界では、スタイルが悪いと見なされることがよくあります。[7]

深さ優先探索

短絡の基本的な例は、二分木の深さ優先探索(DFS)に示されています。標準的な再帰的な議論については、二分木セクションを参照してください

DFSの標準の再帰的アルゴリズムは次のとおりです。

  • 基本ケース:現在のノードがNullの場合、falseを返します
  • 再帰ステップ:それ以外の場合は、現在のノードの値を確認し、一致する場合はtrueを返し、それ以外の場合は子で再帰します

短絡では、これは代わりに次のようになります。

  • 現在のノードの値を確認し、一致する場合はtrueを返します。
  • それ以外の場合、子では、Nullでない場合は、繰り返します。

標準ステップに関しては、これにより、再帰ステップの前にベースケースチェックが移動しますあるいは、これらはそれぞれ、ベースケースと再帰ステップの異なる形式と見なすことができます。これには、ツリー自体が空の場合(ルートノードがNullの場合)を処理するためのラッパー関数が必要であることに注意してください。

高さhの完全な二分木の場合、子として2 h + 1-1ノードと2h +1 Nullポインター(2時間のごとに2つ)があるため、短絡すると関数の数が減ります。最悪の場合、半分に呼び出します。

Cでは、標準の再帰アルゴリズムは次のように実装できます。

bool tree_contains struct node * tree_node int i {      
    if tree_node == NULL    
        falseを返します; //ベースの場合、他の場合tree_node - >データ== I    
        
        trueを返します; 
    そうしないと
        リターンtree_contains tree_node - >私を||   
               tree_contains tree_node- > right i ); 
}

短絡アルゴリズムは次のように実装できます。

//ラッパー関数は、空の木ハンドルに
ブールtree_contains 構造体ノード* tree_nodeをint型のI {      
    if tree_node == NULL    
        falseを返します; //空の木else   
    
        tree_contains_do tree_node i );を返します。//補助関数を呼び出す}    


//は!= NULL tree_nodeを想定してい
BOOL tree_contains_do 構造体のノード* tree_node int型のI {      
    if tree_node- > data == i    
        trueを返します; //他に見つかりまし// recurse return tree_node- > left && tree_contains_do tree_node- > left i ))||   
      
               
               tree_node- > right && tree_contains_do tree_node- > right i ));   
}

ブール&&(AND)演算子の短絡評価使用していることに注意してください。これにより、ノードが有効(Null以外)の場合にのみ再帰呼び出しが行われます。ANDの最初の項はノードへのポインターですが、2番目の項はブール値であるため、式全体がブール値に評価されることに注意してください。これは、再帰的な短絡の一般的なイディオムです。これは、ブール値の短絡評価に追加されます|| (OR)演算子、左の子が失敗した場合にのみ右の子をチェックします。実際、これらの関数の制御フロー全体は、returnステートメントで単一のブール式に置き換えることができますが、読みやすさは効率に悪影響を及ぼしません。

ハイブリッドアルゴリズム

再帰的アルゴリズムは、関数の呼び出しと戻りが繰り返されるオーバーヘッドのため、小さなデータに対しては非効率的であることがよくあります。このため、再帰的アルゴリズムの効率的な実装は、多くの場合、再帰的アルゴリズムから始まりますが、入力が小さくなると別のアルゴリズムに切り替えます。重要な例はマージソートです。これはタイル化されたマージソートのように、データが十分に小さい場合に非再帰的な挿入ソート切り替えることで実装されることがよくありますハイブリッド再帰アルゴリズムは、Timsortのように、ハイブリッドマージソート/挿入ソートから派生してさらに洗練されることがよくあります。

再帰と反復

再帰と反復は同じように表現力があります。再帰は明示的な呼び出しスタックを使用した反復に置き換えることができ、反復は末尾再帰に置き換えることができます。どちらのアプローチが望ましいかは、検討中の問題と使用する言語によって異なります。命令型プログラミング、関数呼び出しとコールスタック管理のオーバーヘッドを回避するように、反復は、特に単純な再帰ため、好ましいが、再帰は、一般的に複数の再帰のために使用されます。対照的に、関数型言語では再帰が優先され、末尾再帰の最適化によってオーバーヘッドがほとんど発生しません。反復を使用してアルゴリズムを実装することは、簡単には達成できない場合があります。

Compare the templates to compute xn defined by xn = f(n, xn-1) from xbase:

function recursive(n)
    if n == base
        return xbase
    else
        return f(n, recursive(n-1))
function iterative(n)
    x = xbase
    for i = base+1 to n
        x = f(i, x)
    return x

For imperative language the overhead is to define the function, for functional language the overhead is to define the accumulator variable x.

For example, a factorial function may be implemented iteratively in C by assigning to a loop index variable and accumulator variable, rather than by passing arguments and returning values by recursion:

unsigned int factorial(unsigned int n) {
  unsigned int product = 1; // empty product is 1
  while (n) {
    product *= n;
    --n;
  }
  return product;
}

Expressive power

Most programming languages in use today allow the direct specification of recursive functions and procedures. When such a function is called, the program's runtime environment keeps track of the various instances of the function (often using a call stack, although other methods may be used). Every recursive function can be transformed into an iterative function by replacing recursive calls with iterative control constructs and simulating the call stack with a stack explicitly managed by the program.[8][9]

Conversely, all iterative functions and procedures that can be evaluated by a computer (see Turing completeness) can be expressed in terms of recursive functions; iterative control constructs such as while loops and for loops are routinely rewritten in recursive form in functional languages.[10][11] However, in practice this rewriting depends on tail call elimination, which is not a feature of all languages. C, Java, and Python are notable mainstream languages in which all function calls, including tail calls, may cause stack allocation that would not occur with the use of looping constructs; in these languages, a working iterative program rewritten in recursive form may overflow the call stack, although tail call elimination may be a feature that is not covered by a language's specification, and different implementations of the same language may differ in tail call elimination capabilities.

Performance issues

In languages (such as C and Java) that favor iterative looping constructs, there is usually significant time and space cost associated with recursive programs, due to the overhead required to manage the stack and the relative slowness of function calls; in functional languages, a function call (particularly a tail call) is typically a very fast operation, and the difference is usually less noticeable.

As a concrete example, the difference in performance between recursive and iterative implementations of the "factorial" example above depends highly on the compiler used. In languages where looping constructs are preferred, the iterative version may be as much as several orders of magnitude faster than the recursive one. In functional languages, the overall time difference of the two implementations may be negligible; in fact, the cost of multiplying the larger numbers first rather than the smaller numbers (which the iterative version given here happens to do) may overwhelm any time saved by choosing iteration.

Stack space

In some programming languages, the maximum size of the call stack is much less than the space available in the heap, and recursive algorithms tend to require more stack space than iterative algorithms. Consequently, these languages sometimes place a limit on the depth of recursion to avoid stack overflows; Python is one such language.[12] Note the caveat below regarding the special case of tail recursion.

Vulnerability

Because recursive algorithms can be subject to stack overflows, they may be vulnerable to pathological or malicious input.[13] Some malware specifically targets a program's call stack and takes advantage of the stack's inherently recursive nature.[14] Even in the absence of malware, a stack overflow caused by unbounded recursion can be fatal to the program, and exception handling logic may not prevent the corresponding process from being terminated.[15]

Multiply recursive problems

Multiply recursive problems are inherently recursive, because of prior state they need to track. One example is tree traversal as in depth-first search; though both recursive and iterative methods are used,[16] they contrast with list traversal and linear search in a list, which is a singly recursive and thus naturally iterative method. Other examples include divide-and-conquer algorithms such as Quicksort, and functions such as the Ackermann function. All of these algorithms can be implemented iteratively with the help of an explicit stack, but the programmer effort involved in managing the stack, and the complexity of the resulting program, arguably outweigh any advantages of the iterative solution.

Refactoring recursion

Recursive algorithms can be replaced with non-recursive counterparts.[17] One method for replacing recursive algorithms is to simulate them using heap memory in place of stack memory.[18] An alternative is to develop a replacement algorithm entirely based on non-recursive methods, which can be challenging.[19] For example, recursive algorithms for matching wildcards, such as Rich Salz' wildmat algorithm,[20] were once typical. Non-recursive algorithms for the same purpose, such as the Krauss matching wildcards algorithm, have been developed to avoid the drawbacks of recursion[21] and have improved only gradually based on techniques such as collecting tests and profiling performance.[22]

Tail-recursive functions

Tail-recursive functions are functions in which all recursive calls are tail calls and hence do not build up any deferred operations. For example, the gcd function (shown again below) is tail-recursive. In contrast, the factorial function (also below) is not tail-recursive; because its recursive call is not in tail position, it builds up deferred multiplication operations that must be performed after the final recursive call completes. With a compiler or interpreter that treats tail-recursive calls as jumps rather than function calls, a tail-recursive function such as gcd will execute using constant space. Thus the program is essentially iterative, equivalent to using imperative language control structures like the "for" and "while" loops.

Tail recursion: Augmenting recursion:
//INPUT: Integers x, y such that x >= y and y >= 0
int gcd(int x, int y)
{
  if (y == 0)
     return x;
  else
     return gcd(y, x % y);
}
//INPUT: n is an Integer such that n >= 0
int fact(int n)
{
   if (n == 0)
      return 1;
   else
      return n * fact(n - 1);
}

The significance of tail recursion is that when making a tail-recursive call (or any tail call), the caller's return position need not be saved on the call stack; when the recursive call returns, it will branch directly on the previously saved return position. Therefore, in languages that recognize this property of tail calls, tail recursion saves both space and time.

Order of execution

Consider these two functions:

Function 1

void recursiveFunction(int num) {
    printf("%d\n", num);
    if (num < 4)
        recursiveFunction(num + 1);
}

Recursive1.svg

Function 2

void recursiveFunction(int num) {
    if (num < 4)
        recursiveFunction(num + 1);
    printf("%d\n", num);
}

Recursive2.svg

Function 2 is function 1 with the lines swapped.

In the case of a function calling itself only once, instructions placed before the recursive call are executed once per recursion before any of the instructions placed after the recursive call. The latter are executed repeatedly after the maximum recursion has been reached.

Also note that the order of the print statements is reversed, which is due to the way the functions and statements are stored on the call stack.

Recursive procedures

Factorial

A classic example of a recursive procedure is the function used to calculate the factorial of a natural number:

Pseudocode (recursive):
function factorial is:
input: integer n such that n >= 0
output: [n × (n-1) × (n-2) × … × 1]
1. if n is 0, return 1 2. otherwise, return [ n × factorial(n-1) ]
end factorial

The function can also be written as a recurrence relation:

This evaluation of the recurrence relation demonstrates the computation that would be performed in evaluating the pseudocode above:

Computing the recurrence relation for n = 4:
b4           = 4 × b3
             = 4 × (3 × b2)
             = 4 × (3 × (2 × b1))
             = 4 × (3 × (2 × (1 × b0)))
             = 4 × (3 × (2 × (1 × 1)))
             = 4 × (3 × (2 × 1))
             = 4 × (3 × 2)
             = 4 × 6
             = 24

This factorial function can also be described without using recursion by making use of the typical looping constructs found in imperative programming languages:

Pseudocode (iterative):
function factorial is:
input: integer n such that n >= 0
output: [n × (n-1) × (n-2) × … × 1]
1. create new variable called running_total with a value of 1
2. begin loop 1. if n is 0, exit loop 2. set running_total to (running_total × n) 3. decrement n 4. repeat loop
3. return running_total
end factorial

The imperative code above is equivalent to this mathematical definition using an accumulator variable t:

The definition above translates straightforwardly to functional programming languages such as Scheme; this is an example of iteration implemented recursively.

Greatest common divisor

The Euclidean algorithm, which computes the greatest common divisor of two integers, can be written recursively.

Function definition:

Pseudocode (recursive):
function gcd is:
input: integer x, integer y such that x > 0 and y >= 0

1. if y is 0, return x 2. otherwise, return [ gcd( y, (remainder of x/y) ) ]
end gcd

Recurrence relation for greatest common divisor, where expresses the remainder of :

if
Computing the recurrence relation for x = 27 and y = 9:
gcd(27, 9)   = gcd(9, 27 % 9)
             = gcd(9, 0)
             = 9
Computing the recurrence relation for x = 111 and y = 259:
gcd(111, 259)   = gcd(259, 111 % 259)
                = gcd(259, 111)
                = gcd(111, 259 % 111)
                = gcd(111, 37)
                = gcd(37, 111 % 37)
                = gcd(37, 0)
                = 37

The recursive program above is tail-recursive; it is equivalent to an iterative algorithm, and the computation shown above shows the steps of evaluation that would be performed by a language that eliminates tail calls. Below is a version of the same algorithm using explicit iteration, suitable for a language that does not eliminate tail calls. By maintaining its state entirely in the variables x and y and using a looping construct, the program avoids making recursive calls and growing the call stack.

Pseudocode (iterative):
function gcd is:
input: integer x, integer y such that x >= y and y >= 0
1. create new variable called remainder
2. begin loop 1. if y is zero, exit loop 2. set remainder to the remainder of x/y 3. set x to y 4. set y to remainder 5. repeat loop
3. return x
end gcd

The iterative algorithm requires a temporary variable, and even given knowledge of the Euclidean algorithm it is more difficult to understand the process by simple inspection, although the two algorithms are very similar in their steps.

Towers of Hanoi

Towers of Hanoi

The Towers of Hanoi is a mathematical puzzle whose solution illustrates recursion.[23][24] There are three pegs which can hold stacks of disks of different diameters. A larger disk may never be stacked on top of a smaller. Starting with n disks on one peg, they must be moved to another peg one at a time. What is the smallest number of steps to move the stack?

Function definition:

Recurrence relation for hanoi:

Computing the recurrence relation for n = 4:
hanoi(4)     = 2×hanoi(3) + 1
             = 2×(2×hanoi(2) + 1) + 1
             = 2×(2×(2×hanoi(1) + 1) + 1) + 1
             = 2×(2×(2×1 + 1) + 1) + 1
             = 2×(2×(3) + 1) + 1
             = 2×(7) + 1
             = 15


Example implementations:

Pseudocode (recursive):
function hanoi is:
input: integer n, such that n >= 1
1. if n is 1 then return 1
2. return [2 * [call hanoi(n-1)] + 1]
end hanoi

Although not all recursive functions have an explicit solution, the Tower of Hanoi sequence can be reduced to an explicit formula.[25]

An explicit formula for Towers of Hanoi:
h1 = 1   = 21 - 1
h2 = 3   = 22 - 1
h3 = 7   = 23 - 1
h4 = 15  = 24 - 1
h5 = 31  = 25 - 1
h6 = 63  = 26 - 1
h7 = 127 = 27 - 1
In general:
hn = 2n - 1, for all n >= 1

Binary search

The binary search algorithm is a method of searching a sorted array for a single element by cutting the array in half with each recursive pass. The trick is to pick a midpoint near the center of the array, compare the data at that point with the data being searched and then responding to one of three possible conditions: the data is found at the midpoint, the data at the midpoint is greater than the data being searched for, or the data at the midpoint is less than the data being searched for.

Recursion is used in this algorithm because with each pass a new array is created by cutting the old one in half. The binary search procedure is then called recursively, this time on the new (and smaller) array. Typically the array's size is adjusted by manipulating a beginning and ending index. The algorithm exhibits a logarithmic order of growth because it essentially divides the problem domain in half with each pass.

Example implementation of binary search in C:

 /*
  Call binary_search with proper initial conditions.

  INPUT:
    data is an array of integers SORTED in ASCENDING order,
    toFind is the integer to search for,
    count is the total number of elements in the array

  OUTPUT:
    result of binary_search

 */
 int search(int *data, int toFind, int count)
 {
    //  Start = 0 (beginning index)
    //  End = count - 1 (top index)
    return binary_search(data, toFind, 0, count-1);
 }

 /*
   Binary Search Algorithm.

   INPUT:
        data is a array of integers SORTED in ASCENDING order,
        toFind is the integer to search for,
        start is the minimum array index,
        end is the maximum array index
   OUTPUT:
        position of the integer toFind within array data,
        -1 if not found
 */
 int binary_search(int *data, int toFind, int start, int end)
 {
    //Get the midpoint.
    int mid = start + (end - start)/2;   //Integer division


    if (start > end)                     //Stop condition (base case)
       return -1;
    else if (data[mid] == toFind)        //Found, return index
       return mid;
    else if (data[mid] > toFind)         //Data is greater than toFind, search lower half
       return binary_search(data, toFind, start, mid-1);
    else                                 //Data is less than toFind, search upper half
       return binary_search(data, toFind, mid+1, end);
 }

Recursive data structures (structural recursion)

An important application of recursion in computer science is in defining dynamic data structures such as lists and trees. Recursive data structures can dynamically grow to a theoretically infinite size in response to runtime requirements; in contrast, the size of a static array must be set at compile time.

"Recursive algorithms are particularly appropriate when the underlying problem or the data to be treated are defined in recursive terms."[26]

The examples in this section illustrate what is known as "structural recursion". This term refers to the fact that the recursive procedures are acting on data that is defined recursively.

As long as a programmer derives the template from a data definition, functions employ structural recursion. That is, the recursions in a function's body consume some immediate piece of a given compound value.[6]

Linked lists

Below is a C definition of a linked list node structure. Notice especially how the node is defined in terms of itself. The "next" element of struct node is a pointer to another struct node, effectively creating a list type.

struct node
{
  int data;           // some integer data
  struct node *next;  // pointer to another struct node
};

Because the struct node data structure is defined recursively, procedures that operate on it can be implemented naturally as recursive procedures. The list_print procedure defined below walks down the list until the list is empty (i.e., the list pointer has a value of NULL). For each node it prints the data element (an integer). In the C implementation, the list remains unchanged by the list_print procedure.

void list_print(struct node *list)
{
    if (list != NULL)               // base case
    {
       printf ("%d ", list->data);  // print integer data followed by a space
       list_print (list->next);     // recursive call on the next node
    }
}

Binary trees

Below is a simple definition for a binary tree node. Like the node for linked lists, it is defined in terms of itself, recursively. There are two self-referential pointers: left (pointing to the left sub-tree) and right (pointing to the right sub-tree).

struct node
{
  int data;            // some integer data
  struct node *left;   // pointer to the left subtree
  struct node *right;  // point to the right subtree
};

Operations on the tree can be implemented using recursion. Note that because there are two self-referencing pointers (left and right), tree operations may require two recursive calls:

// Test if tree_node contains i; return 1 if so, 0 if not.
int tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return 0;  // base case
    else if (tree_node->data == i)
        return 1;
    else
        return tree_contains(tree_node->left, i) || tree_contains(tree_node->right, i);
}

At most two recursive calls will be made for any given call to tree_contains as defined above.

// Inorder traversal:
void tree_print(struct node *tree_node) {
    if (tree_node != NULL) {              // base case
        tree_print(tree_node->left);      // go left
        printf("%d ", tree_node->data);   // print the integer followed by a space
        tree_print(tree_node->right);     // go right
    }
}

The above example illustrates an in-order traversal of the binary tree. A Binary search tree is a special case of the binary tree where the data elements of each node are in order.

Filesystem traversal

Since the number of files in a filesystem may vary, recursion is the only practical way to traverse and thus enumerate its contents. Traversing a filesystem is very similar to that of tree traversal, therefore the concepts behind tree traversal are applicable to traversing a filesystem. More specifically, the code below would be an example of a preorder traversal of a filesystem.

import java.io.File;

public class FileSystem {

	public static void main(String [] args) {
		traverse();
	}

	/**
	 * Obtains the filesystem roots
	 * Proceeds with the recursive filesystem traversal
	 */
	private static void traverse() {
		File[] fs = File.listRoots();
		for (int i = 0; i < fs.length; i++) {
			System.out.println(fs[i]);
			if (fs[i].isDirectory() && fs[i].canRead()) {
				rtraverse(fs[i]);
			}
		}
	}

	/**
	 * Recursively traverse a given directory
	 *
	 * @param fd indicates the starting point of traversal
	 */
	private static void rtraverse(File fd) {
		File[] fss = fd.listFiles();

		for (int i = 0; i < fss.length; i++) {
			System.out.println(fss[i]);
			if (fss[i].isDirectory() && fss[i].canRead()) {
				rtraverse(fss[i]);
			}
		}
	}

}

This code is both recursion and iteration - the files and directories are iterated, and each directory is opened recursively.

The "rtraverse" method is an example of direct recursion, whilst the "traverse" method is a wrapper function.

The "base case" scenario is that there will always be a fixed number of files and/or directories in a given filesystem.

Time-efficiency of recursive algorithms

The time efficiency of recursive algorithms can be expressed in a recurrence relation of Big O notation. They can (usually) then be simplified into a single Big-O term.

Shortcut rule (master theorem)

If the time-complexity of the function is in the form

Then the Big O of the time-complexity is thus:

  • If for some constant , then
  • If , then
  • If for some constant , and if for some constant c < 1 and all sufficiently large n, then

where a represents the number of recursive calls at each level of recursion, b represents by what factor smaller the input is for the next level of recursion (i.e. the number of pieces you divide the problem into), and f (n) represents the work the function does independent of any recursion (e.g. partitioning, recombining) at each level of recursion.

See also

Notes

  1. ^ Graham, Ronald; Knuth, Donald; Patashnik, Oren (1990). "1: Recurrent Problems". Concrete Mathematics. ISBN 0-201-55802-5.
  2. ^ Epp, Susanna (1995). Discrete Mathematics with Applications (2nd ed.). p. 427. ISBN 978-0-53494446-9.
  3. ^ Wirth, Niklaus (1976). Algorithms + Data Structures = Programs. Prentice-Hall. p. 126. ISBN 978-0-13022418-7.
  4. ^ "Functional Programming | Clojure for the Brave and True". www.braveclojure.com. Retrieved 2020-10-21.
  5. ^ Felleisen et al. 2001, art V "Generative Recursion
  6. ^ a b Felleisen, Matthias (2002). "Developing Interactive Web Programs". In Jeuring, Johan (ed.). Advanced Functional Programming: 4th International School (PDF). Springer. p. 108. ISBN 9783540448334.
  7. ^ Mongan, John; Giguère, Eric; Kindler, Noah (2013). Programming Interviews Exposed: Secrets to Landing Your Next Job (3rd ed.). Wiley. p. 115. ISBN 978-1-118-26136-1.
  8. ^ Hetland, Magnus Lie (2010), Python Algorithms: Mastering Basic Algorithms in the Python Language, Apress, p. 79, ISBN 9781430232384.
  9. ^ Drozdek, Adam (2012), Data Structures and Algorithms in C++ (4th ed.), Cengage Learning, p. 197, ISBN 9781285415017.
  10. ^ Shivers, Olin. "The Anatomy of a Loop - A story of scope and control" (PDF). Georgia Institute of Technology. Retrieved 2012-09-03.
  11. ^ Lambda the Ultimate. "The Anatomy of a Loop". Lambda the Ultimate. Retrieved 2012-09-03.
  12. ^ "27.1. sys — System-specific parameters and functions — Python v2.7.3 documentation". Docs.python.org. Retrieved 2012-09-03.
  13. ^ Krauss, Kirk J. (2014). "Matching Wildcards: An Empirical Way to Tame an Algorithm". Dr. Dobb's Journal.
  14. ^ Mueller, Oliver (2012). "Anatomy of a Stack Smashing Attack and How GCC Prevents It". Dr. Dobb's Journal.
  15. ^ "StackOverflowException Class". .NET Framework Class Library. Microsoft Developer Network. 2018.
  16. ^ "Depth First Search (DFS): Iterative and Recursive Implementation". Techie Delight. 2018.
  17. ^ Mitrovic, Ivan. "Replace Recursion with Iteration". ThoughtWorks.
  18. ^ La, Woong Gyu (2015). "How to replace recursive functions using stack and while-loop to avoid the stack-overflow". CodeProject.
  19. ^ Moertel, Tom (2013). "Tricks of the trade: Recursion to Iteration, Part 2: Eliminating Recursion with the Time-Traveling Secret Feature Trick".
  20. ^ Salz, Rich (1991). "wildmat.c". GitHub.
  21. ^ Krauss, Kirk J. (2008). "Matching Wildcards: An Algorithm". Dr. Dobb's Journal.
  22. ^ Krauss, Kirk J. (2018). "Matching Wildcards: An Improved Algorithm for Big Data". Develop for Performance.
  23. ^ Graham, Knuth & Patashnik 1990, §1.1: The Tower of Hanoi
  24. ^ Epp 1995, pp. 427–430: The Tower of Hanoi
  25. ^ Epp 1995, pp. 447–448: An Explicit Formula for the Tower of Hanoi Sequence
  26. ^ Wirth 1976, p. 127

References