再帰（コンピュータサイエンス）

基本ケースは、関数がそれ以上の再帰なしに結果を直接提供できる入力値を指定します。^{[ 11 ]}これらは通常、最も単純または最小の入力（簡単に解けるもの）であり、計算を終了させることができます。基本ケースは無限後退を防ぐため不可欠です。言い換えれば、再帰を終了する停止条件を定義します。

例えば、整数 n の階乗を計算する場合を考えてみましょう。階乗とは、0 から n までのすべての整数の積です。この問題では、0! = 1 という定義が基本ケースとなります。この定義がないと、再帰が無限に続き、実際の実装では終了しない、あるいはスタックオーバーフローエラーが発生する可能性が高くなります。

正しいベースケースを設計することは、理論的にも実践的にも非常に重要です。問題によっては自然なベースケースが存在するもの（例えば、空のリストは一部の再帰的なリスト処理関数におけるベースケース）もあれば、停止条件を示すための追加パラメータを必要とするもの（例えば、再帰的なツリー走査における深さカウンタの使用）もあります。

再帰的なコンピュータプログラミングでは、基本ケースを省略したり、定義を誤ったりすると、意図しない無限再帰が発生する可能性があります。ある研究では、多くの学生が適切な基本ケースを特定するのに苦労していることが研究者によって示されました。^{[ 11 ]}

再帰ケースは、問題を同じ形式のより小さなサブ問題に分解する方法を説明しています。^{[ 11 ]}各再帰ステップは、入力をベースケースに近づけるように変換し、終了に向けての進行を保証します。削減ステップがベースケースに向かって進行しない場合、アルゴリズムは無限ループに陥る可能性があります。

階乗の例では、再帰的なケースは次のように定義されます。 ${\displaystyle n!=n\cdot (n-1)!\,,\forall n>0.}$ ここでは、関数の呼び出しごとに入力が減少します。${\displaystyle n}$1. これにより、再帰が最終的に基本ケースに到達することが保証されます。${\displaystyle n=0}$。

再帰的なケースは、帰納法による証明における帰納的ステップに類似しています。つまり、関数がより小さなインスタンスで正しく機能することを前提とし、その前提を現在の入力に拡張します。したがって、再帰的な定義とアルゴリズムは、数学における帰納的議論と非常に類似しており、その正当性はしばしば同様の推論手法に依存します。

再帰には、基本ケースと再帰ケースの構造に従う実用的な応用例がいくつか存在する。これらは、コンピュータサイエンスにおける複雑な問題を解決するために広く用いられている。

• 深さ優先探索などのツリー走査では、各サブツリーを処理するために再帰ケースを使用し（再帰ケース）、最終的に葉ノードで停止します（基本ケース）。^{[ 12 ]}
• マージソートは、分割された部分配列を再帰的にソートおよびマージし（再帰ケース）、各部分配列が1つの要素で構成されるまで（基本ケース）繰り返すソートアルゴリズムです。 ^{[ 13 ]}
• フィボナッチ数列は、数列の前の2つの数を足し合わせることによって定義され（再帰の場合）、n = 0 または n = 1 のときに停止します（基本の場合）。
• 二分探索では、ターゲットが見つかるか、探索区間が空になるまで（基本ケース）、探索区間を繰り返し半分に分割します（再帰ケース）。

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

data ListOfStrings = EmptyList | Cons String ListOfStrings

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

帰納的定義のもう一つの例は、自然数（または正の整数）です。

自然数とは、1またはn+1のいずれかであり、nは自然数である。

同様に、再帰的な定義は、プログラミング言語における式や文の構造をモデル化するためによく用いられます。言語設計者は、文法をバッカス・ナウア記法などの構文で表現することがよくあります。以下は、乗算と加算を含む単純な算術式の言語における文法の一例です。

<式> ::= <数値> | ( <式> * <式> ) | ( <式> + <式> ) 

これは、式が数値、2つの式の積、または2つの式の和のいずれかであることを示しています。2行目と3行目の式を再帰的に参照することで、この文法は、(5 * ((3 * 6) + 8))1つの式の中に複数の積または和演算を含む、任意の複雑な算術式（例：）を許容します。

共帰納的データ定義とは、あるデータに対して実行可能な操作を指定する定義のことです。一般的に、自己参照的な共帰納的定義は、無限サイズのデータ​​構造に使用されます。

非公式に与えられた無限の文字列の流れの帰納的定義は、次のようになるかもしれない。

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

これは文字列リストの帰納的定義と非常によく似ています。違いは、この定義ではデータ構造の内容にアクセスする方法（つまり、アクセサ関数を介して）とhead、tailその内容が何であるかを指定するのに対し、帰納的定義では構造を作成する方法と、それが何から作成されるかを指定する点です。

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

自己参照が1つだけ含まれる再帰は、単一の再帰、一方、複数の自己参照を含む再帰は、多重再帰。単一再帰の標準的な例としては、線形探索におけるリストの走査や階乗関数の計算などがあり、多重再帰の標準的な例としては、深さ優先探索におけるツリーの走査

単一再帰は多くの場合、複数再帰よりもはるかに効率的であり、一般的には反復計算で置き換えることができ、線形時間で実行され、一定のメモリ領域しか必要としません。一方、複数再帰は指数関数的な時間とメモリ領域を必要とする場合があり、より根本的に再帰的であるため、明示的なスタックなしでは反復処理で置き換えることはできません。

多重再帰は、場合によっては単一の再帰（そして必要に応じて反復）に変換できます。例えば、フィボナッチ数列を計算するには、各値に前の2つの値が必要となるため、単純には多重反復が必要になりますが、連続する2つの値をパラメータとして渡すことで、単一の再帰で計算できます。

再帰の最も基本的な例、そしてここで紹介する例のほとんどは、直接再帰とは、関数が自身を呼び出すことです。 間接再帰とは、関数が自身ではなく、関数が呼び出した別の関数（直接または間接的に）によって呼び出される場合に発生します。たとえば、 f がf を呼び出すは直接再帰ですが、 f がgを呼び出し、g が fを呼び出すは、f の間接再帰です。3つ以上の関数の連鎖も可能です。たとえば、関数 1 が関数 2 を呼び出し、関数 2 が関数 3 を呼び出し、関数 3 が再び関数 1 を呼び出す場合などです。

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

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

再帰を「構造的」または「生成的」に分類する著者もいる。この区別は、再帰的な手続きが処理対象のデータをどこから取得し、どのように処理するかに関係している。

構造化データを処理する関数は、通常、引数をその直接の構造的構成要素に分解し、それらの構成要素を処理します。直接の構成要素のいずれかが入力と同じクラスのデータに属する場合、その関数は再帰的です。そのため、これらの関数を（構造的に）再帰的な関数と呼びます。

したがって、構造的に再帰的な関数の決定的な特徴は、各再帰呼び出しの引数が元の入力のフィールドの内容であることです。構造的再帰には、XML処理、二分木の作成と検索など、ほぼすべてのツリー走査が含まれます。自然数の代数的構造（つまり、自然数はゼロか、自然数の次の数のいずれかである）を考慮すると、階乗などの関数も構造的再帰とみなすことができます。

生成再帰は代替手段である。

多くの有名な再帰アルゴリズムは、与えられたデータから全く新しいデータを生成し、それに対して再帰処理を行います。HtDP （ How to Design Programs）では、このようなアルゴリズムを生成再帰と呼んでいます。生成再帰の例としては、最大公約数、クイックソート、二分探索、マージソート、ニュートン法、フラクタル、適応積分などがあります。

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

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

ラッパー関数とは、直接呼び出される関数ですが、自身は再帰処理を行わず、代わりに別の補助関数を呼び出し、その補助関数が実際に再帰処理を実行します。

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

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

短絡評価は、ツリー内のヌルポインタなど、多くの基本ケースが発生する場合に主に重要となります。基本ケースは関数呼び出しの数に比例するため、O ( n )アルゴリズムでは大幅な節約になります。これは、深さ優先探索の場合に以下に示します。ツリーでの短絡評価は、空ノードを基本ケースとするのではなく、葉ノード（​​子ノードを持たない空でないノード）を基本ケースとみなすことに相当します。階乗の計算のように基本ケースが 1 つしかない場合は、短絡評価による節約はO (1)にしかなりません。

概念的には、短絡は、同じ基本ケースと再帰ステップを持ち、再帰の前に基本ケースのみをチェックするものと考えることも、異なる基本ケース（標準の基本ケースから1ステップ離れたもの）とより複雑な再帰ステップ、つまり「有効性をチェックしてから再帰する」ものと考えることもできます。これは、ツリーの基本ケースとしてNullノードではなくリーフノードを考慮する場合と同様です。短絡は、標準的な再帰における基本ケースと再帰ステップの明確な分離と比較して、より複雑な流れを持つため、特に学術界では、しばしば不適切なスタイルとみなされます。^{[ 16 ]}

bool tree_contains ( struct BinaryTree * node , int i ) { if ( ! node ) { return false ; // 基本ケース} else if ( node -> data == i ) { return true ; } else { return tree_contains ( node -> left , i ) || tree_contains ( node -> right , i ); } }

#include <assert.h>// 空のツリーを処理するためのラッパー関数bool tree_contains ( struct BinaryTree * node , int i ) { if ( ! node ) { return false ; // 空のツリー} else { return tree_contains_aux ( node , i ); // 補助関数を呼び出す} }// node != NULL を前提とするbool tree_contains_aux ( struct BinaryTree * node , int i ) { assert ( node ); if ( node -> data == i ) { return true ; // 見つかった} else { // 再帰return ( node -> left && tree_contains_aux ( node -> left , i )) || ( node -> right && tree_contains_aux ( node -> right , i )); } }

再帰アルゴリズムは、関数呼び出しと戻り値の繰り返しによるオーバーヘッドのため、データ量が少ない場合には非効率になることが多い。そのため、効率的な再帰アルゴリズムの実装では、まず再帰アルゴリズムから始め、入力データが小さくなった時点で別のアルゴリズムに切り替えることが多い。重要な例としてマージソートが挙げられる。マージソートは、タイルマージソートのように、データが十分に小さくなった時点で非再帰的な挿入ソートに切り替えることで実装されることが多い。ハイブリッド再帰アルゴリズムは、ハイブリッドマージソートと挿入ソートを組み合わせたTimsortのように、さらに改良できる場合が多い。

今日使用されているほとんどのプログラミング言語では、再帰関数とプロシージャを直接指定できます。このような関数が呼び出されると、プログラムの実行環境は関数のさまざまなインスタンスを追跡します（多くの場合、コールスタックを使用しますが、他の方法を使用することもできます）。すべての再帰関数は、再帰呼び出しを反復制御構造に置き換え、コールスタックをプログラムによって明示的に管理されるスタックでシミュレートすることにより、反復関数に変換できます。 ^{[ 17 ] [ 18 ]}

逆に、コンピュータで評価できるすべての反復関数と手順 (チューリング完全性を参照) は再帰関数で表現できます。whileループやfor ループなどの反復制御構造は、関数型言語では日常的に再帰形式で書き直されます。^{[ 19 ] [ 20 ]}ただし、実際にはこの書き直しは末尾呼び出し除去に依存しますが、これはすべての言語の機能ではありません。C 、Java、Python は、末尾呼び出しを含むすべての関数呼び出しがループ構造を使用した場合に発生しないスタック割り当てを引き起こす可能性がある、注目すべき主流言語です。これらの言語では、末尾呼び出し除去が言語の仕様でカバーされていない機能である場合や、同じ言語の異なる実装で末尾呼び出し除去機能が異なる場合があるにもかかわらず、再帰形式で書き直された動作する反復プログラムが呼び出しスタックをオーバーフローする可能性があります。

反復ループ構造を好む言語（ CやJavaなど）では、スタックの管理に必要なオーバーヘッドや関数呼び出しの相対的な遅さのため、再帰プログラムには通常、かなりの時間と空間のコストがかかります。一方、関数型言語では、関数呼び出し（特に末尾呼び出し）は通常非常に高速な操作であり、その差はあまり目立ちません。

具体的な例として、上記の「階乗」の例の再帰的実装と反復的実装のパフォーマンスの違いは、使用するコンパイラに大きく依存します。ループ構造が好まれる言語では、反復的バージョンは再帰的バージョンよりも数桁も高速になる可能性があります。関数型言語では、2つの実装の全体的な時間差は無視できるほど小さいかもしれません。実際、（ここで示した反復的バージョンが行っているように）小さい数よりも大きい数を先に掛けるコストが、反復を選択することで節約できる時間を上回ってしまう可能性があります。

一部のプログラミング言語では、コールスタックの最大サイズがヒープで使用可能なスペースよりもはるかに小さく、再帰アルゴリズムは反復アルゴリズムよりも多くのスタックスペースを必要とする傾向があります。そのため、これらの言語ではスタックオーバーフローを避けるために再帰の深さに制限を設けることがあります。Pythonはそのような言語の 1 つです。^{[ 21 ]}末尾再帰の特殊なケースについては、以下の注意書きに注意してください。

再帰アルゴリズムはスタックオーバーフローを起こす可能性があるため、病的な入力や悪意のある入力に対して脆弱である可能性があります。^{[ 22 ]}一部のマルウェアは、プログラムのコールスタックを特に標的とし、スタックの本来の再帰的な性質を利用します。^{[ 23 ]}マルウェアがない場合でも、無制限の再帰によって引き起こされるスタックオーバーフローはプログラムにとって致命的となる可能性があり、例外処理ロジックが対応するプロセスの終了を防げない場合があります。^{[ 24 ]}

多重再帰問題は、追跡する必要のある以前の状態があるため、本質的に再帰的です。 1 つの例として、深さ優先探索のようなツリーの走査があります。再帰的方法と反復的方法の両方が使用されますが、^{[ 25 ]}リストの走査やリスト内の線形探索とは対照的です。リストの走査や線形探索は単一の再帰であり、したがって自然に反復的な方法です。 他の例としては、クイックソートなどの分割統治アルゴリズムや、アッカーマン関数などの関数があります。 これらのアルゴリズムはすべて、明示的なスタックの助けを借りて反復的に実装できますが、スタックの管理に伴うプログラマの労力と、結果として得られるプログラムの複雑さは、反復ソリューションの利点を上回る可能性があります。

再帰アルゴリズムは、非再帰アルゴリズムに置き換えることができます。^{[ 26 ]}再帰アルゴリズムを置き換える方法の 1 つは、スタック メモリの代わりにヒープ メモリを使用してシミュレートすることです。^{[ 27 ]}代替案は、完全に非再帰的な方法に基づいて代替アルゴリズムを開発することですが、これは困難な場合があります。^{[ 28 ]}例えば、Rich Salzのwildmatアルゴリズム^{[ 29 ]}のようなワイルドカードのマッチングのための再帰アルゴリズムは、かつては一般的でした。同じ目的のための非再帰アルゴリズム、例えばKrauss のワイルドカード マッチング アルゴリズムは、再帰の欠点を回避するために開発され^{[ 30 ]} 、テストの収集やパフォーマンスのプロファイリングなどの技術に基づいて徐々に改善されてきました。^{[ 31 ]}

#include <stdio.h>void recursiveFunction ( int num ) { if ( num < 4 ) { recursiveFunction ( num + 1 ); } printf ( "%d \n " , num ); }

関数2の出力は、関数1の出力の行を入れ替えたものです。

関数が自身を一度だけ呼び出す場合、再帰呼び出しの前に配置された命令は、再帰呼び出しの後に配置された命令よりも先に、再帰ごとに一度実行されます。再帰呼び出しの後に配置された命令は、最大再帰回数に達した後に繰り返し実行されます。

また、 print文の順序が逆になっていることにも注意してください。これは、関数と文がコールスタックに格納される方法によるものです。

再帰的手続きの典型的な例は、自然数の階乗を計算するために使用される関数です。

${\displaystyle \operatorname {fact} (n)={\begin{cases}1&{\mbox{if }}n=0\\n\cdot \operatorname {fact} (n-1)&{\mbox{if }}n>0\\\end{cases}}}$

この関数は漸化式としても表すことができます。

${\displaystyle b_{n}=nb_{n-1}}$

${\displaystyle b_{0}=1}$

この漸化式の評価は、上記の擬似コードを評価する際に実行される計算を示しています。

この階乗関数は、命令型プログラミング言語によく見られるループ構造を利用することで、再帰を用いずに記述することもできます。

上記の命令型コードは、アキュムレータ変数tを使用した以下の数学的定義と同等です。

${\displaystyle {\begin{aligned}\operatorname {fact} (n)&=\operatorname {fact_{acc}} (n,1)\\\operatorname {fact_{acc}} (n,t)&={\begin{cases}t&{\mbox{if }}n=0\\\operatorname {fact_{acc}} (n-1,nt)&{\mbox{if }}n>0\\\end{cases}}\end{aligned}}}$

上記の定義は、 Schemeのような関数型プログラミング言語にそのまま適用できます。これは、再帰的に実装された反復処理の一例です。

2つの整数の最大公約数を計算するユークリッドの互除法は、再帰的に記述することができる。

関数定義：

${\displaystyle \gcd(x,y)={\begin{cases}x&{\mbox{if }}y=0\\\gcd(y,\operatorname {remainder} (x,y))&{\mbox{if }}y>0\\\end{cases}}}$

最大公約数に関する漸化式、ここで${\displaystyle x\%y}$残りの​${\displaystyle x/y}$:

${\displaystyle \gcd(x,y)=\gcd(y,x\%y)}$もし${\displaystyle y\neq 0}$

${\displaystyle \gcd(x,0)=x}$

上記の再帰プログラムは末尾再帰です。これは反復アルゴリズムと同等であり、上記の計算は末尾呼び出しを排除する言語で実行される評価手順を示しています。以下は、末尾呼び出しを排除しない言語に適した、明示的な反復を使用した同じアルゴリズムのバージョンです。このプログラムは、状態を変数xとyに完全に保持し、ループ構造を使用することで、再帰呼び出しと呼び出しスタックの増大を回避しています。

反復アルゴリズムは一時変数を必要とし、ユークリッドの互除法の知識があっても、手順は非常に似ているものの、単純な観察だけでそのプロセスを理解するのはより困難である。

ハノイの塔は、再帰を例示する数学パズルです。^{[ 32 ] [ 33 ]}直径の異なる円盤を積み重ねることができる杭が3つあります。大きい円盤を小さい円盤の上に積み重ねることはできません。1つの杭にn個の円盤がある状態から始め、1つずつ別の杭に移動する必要があります。積み重ねた円盤を移動させる最小ステップ数はいくつですか？

関数定義：

${\displaystyle \operatorname {hanoi} (n)={\begin{cases}1&{\mbox{if }}n=1\\2\cdot \operatorname {hanoi} (n-1)+1&{\mbox{if }}n>1\\\end{cases}}}$

ハノイの漸化式：

${\displaystyle h_{n}=2h_{n-1}+1}$

${\displaystyle h_{1}=1}$

実装例：

すべての再帰関数に明示的な解があるわけではないが、ハノイの塔の数列は明示的な式に還元できる。^{[ 34 ]}

二分探索アルゴリズムは、再帰的に配列を半分に分割しながら、ソート済みの配列から単一の要素を検索する方法です。そのコツは、配列の中央付近にある中間点を選択し、その点のデータを検索対象のデータと比較し、次の3つの条件のいずれかに応答することです。中間点にデータが見つかった場合、中間点のデータが検索対象のデータより大きい場合、または中間点のデータが検索対象のデータより小さい場合です。

このアルゴリズムでは再帰が用いられています。なぜなら、各パスで古い配列を半分に分割することで新しい配列が作成されるからです。その後、バイナリサーチの手順が再帰的に呼び出され、今度は新しい（より小さい）配列に対して実行されます。通常、配列のサイズは開始インデックスと終了インデックスを操作することで調整されます。このアルゴリズムは、各パスで問題領域を実質的に半分に分割するため、対数的な成長を示します。

C言語による二分探索の実装例：

/** * @brief 適切な初期条件を指定して binary_search を呼び出します。* @param data 昇順にソートされた整数の配列* @param target 検索対象の整数* @param count 配列内の要素の総数* @returns binary_search の結果*/ int search ( int data [], int target , int count ) { // Start = 0 (開始インデックス) // End = count - 1 (最上位インデックス) return binary_search ( data , target , 0 , count - 1 ); }/** * @brief 二分探索アルゴリズム。* @param data 昇順にソートされた整数の配列* @param target 検索する整数* @param start 配列の最小インデックス* @param end 配列の最大インデックス* @returns 配列データ内で検索する整数の位置。見つからない場合は -1 */ int binary_search ( int data [], int target , int start , int end ) { // 中間点を取得します。int mid = start + ( end - start ) / 2 ; // 整数除算if ( start > end ) { return -1 ; // 停止条件 (基本ケース) } else if ( data [ mid ] == target ) { return mid ; // 見つかったので、インデックスを返す} else if ( data [ mid ] > target ) { // データがターゲットより大きいので、下半分を検索return binary_search ( data , target , start , mid - 1 ); } else { // データがターゲットより小さいので、上半分を検索return binary_search ( data , target , mid + 1 , end ); } }

以下は、連結リストのノード構造のC言語による定義です。特に、ノードが自身を用いてどのように定義されているかに注目してください。「next」要素はLinkedList別の連結リストへのポインタであり、実質的にリスト型を作成します。

struct LinkedList { int data ; // 整数データstruct LinkedList * next ; // リンクリストの別のノードへのポインタ};

struct nodeデータ構造は再帰的に定義されているため、この構造を操作するプロシージャは自然に再帰的なプロシージャとして実装できます。以下に定義するlist_printプロシージャは、リストが空になるまで (つまり、リストポインタの値が NULL になるまで) リストを順に処理します。各ノードについて、データ要素 (整数) を出力します。C 言語の実装では、list_printプロシージャによってリストは変更されません。

void list_print ( struct LinkedList * list ) { // 基本ケースif ( list ) { printf ( "%d " , list -> data ); // 整数データの後にスペースを出力list_print ( list -> next ); // 次のノードで再帰呼び出し} }

以下は、二分木ノードの簡単な定義です。連結リストのノードと同様に、再帰的に自身に基づいて定義されます。自己参照ポインタは2つあり、left（左サブツリーを指す）とright（右サブツリーを指す）です。

struct BinaryTree { int data ; // 整数データstruct BinaryTree * left ; // 左サブツリーへのポインタstruct BinaryTree * right ; // 右サブツリーへのポインタ};

ツリーに対する操作は再帰を用いて実装できます。ただし、自己参照ポインタが2つ（左と右）存在するため、ツリー操作には2回の再帰呼び出しが必要になる場合があることに注意してください。

// tree_node に i が含まれているかどうかをテストします。含まれている場合は 1 を、含まれていない場合は 0 を返します。int tree_contains ( struct BinaryTree * node , int i ) { if ( ! node ) { return 0 ; //基本ケース} else if ( node - > data == i ) { return 1 ; } else { return tree_contains ( node -> left , i ) || tree_contains ( node -> right , i ); } }

上記で定義したtree_containsへの呼び出しごとに、最大で2回の再帰呼び出しが行われます。

// 中順走査: void tree_print ( struct BinaryTree * node ) { // 基本ケースif ( node ) { tree_print ( node -> left ); // 左へ進むprintf ( "%d " , node -> data ); // 整数とスペースを出力するtree_print ( node -> right ); // 右へ進む} }

上記の例は、二分木の順序通りの走査を示しています。二分探索木は、各ノードのデータ要素が順序通りに格納されている二分木の特殊なケースです。

ファイルシステム内のファイル数は変動する可能性があるため、その内容を走査して列挙するには再帰が唯一実用的な方法です。ファイルシステムの走査はツリー走査と非常によく似ているため、ツリー走査の概念はファイルシステムの走査にも適用できます。より具体的には、以下のコードはファイルシステムの先行順走査の例となります。

パッケージorg.wikipedia.examples ;import java.io.File ;public class Example { /**  * ファイルシステムのルートを取得します * 再帰的なファイルシステム走査を実行します */ 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 ] ); } } }/**  * 指定されたディレクトリを再帰的に走査します *  * @param fd 走査の開始点を示します */ 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 ] ); } } }public static void main ( String [] args ) { traverse (); } }

このコードは再帰と反復の両方を含んでいます。ファイルとディレクトリが反復処理され、各ディレクトリが再帰的に開かれます。

「rtraverse」メソッドは直接再帰の一例であり、「traverse」メソッドはラッパー関数である。

「基本ケース」のシナリオは、特定のファイルシステムには常に一定数のファイルやディレクトリが存在するというものです。

関数の時間計算量が次の形式である場合 $${\displaystyle T(n)=a\cdot T(n/b)+f(n)}$$

すると、時間計算量のビッグオー記法は次のようになる。

• もし${\displaystyle f(n)=O(n^{\log _{b}a-\varepsilon })}$ある定数に対して${\displaystyle \varepsilon >0}$、 それから${\displaystyle T(n)=\Theta (n^{\log _{b}a})}$
• もし${\displaystyle f(n)=\Theta (n^{\log _{b}a})}$、 それから${\displaystyle T(n)=\Theta (n^{\log _{b}a}\log n)}$
• もし${\displaystyle f(n)=\Omega (n^{\log _{b}a+\varepsilon })}$ある定数に対して${\displaystyle \varepsilon >0}$、そしてもし${\displaystyle a\cdot f(n/b)\leq c\cdot f(n)}$ある定数c < 1および十分大きなnに対して、${\displaystyle T(n)=\Theta (f(n))}$

ここで、a は各再帰レベルでの再帰呼び出しの数を表し、b は次の再帰レベルの入力がどれだけ小さくなるか（つまり、問題を分割する部分の数）を表し、f ( n )は各再帰レベルで関数が再帰とは独立して行う作業（分割、再結合など）を表します。