相互再帰

数学とコンピュータサイエンスにおいて、相互再帰は、関数やデータ型などの2つの数学的または計算的オブジェクトが互いの観点から定義される再帰の一形態です。 ^{[1]相互再帰は、}関数型プログラミングや、データ型が自然に相互再帰である再帰下降パーサーなどの一部の問題領域で非常に一般的です。

相互再帰によって定義できるデータ型の最も重要な基本的な例は、フォレスト (ツリーのリスト) の観点から相互再帰的に定義できる ツリーです。記号的には次のようになります。

f: [t[1], ..., t[k]]
t: ヴフ

フォレストf はツリーのリストで構成され、ツリーt は値vとフォレストf (その子)のペアで構成されます。この定義は簡潔で抽象的に扱いやすく (ツリーの特性に関する定理を証明する場合など)、ツリーを単純な言葉で表現します (1 つのタイプのリストと 2 つのタイプのペア)。さらに、これはツリー上の多くのアルゴリズムと一致し、値に対して 1 つの処理を行い、子に対して別の処理を行います。

この相互再帰定義は、フォレストの定義を インライン化することで単一再帰定義に変換できます。

t: v[t[1], ..., t[k]]

ツリーt は、値vとツリーのリスト (その子) のペアで構成されます。この定義はより簡潔ですが、やや複雑です。ツリーは、あるタイプのペアと別のタイプのリストから構成され、結果を証明するにはそれらを分離する必要があります。

標準MLでは、ツリーとフォレストのデータ型は次のように相互に再帰的に定義され、空のツリーが許可されます。^[2]

データ型 'a  tree  =  Empty  |  'a * 'a forestのノード と'a forest = Nil | 'a tree * 'a forestの短所    
                 

再帰データ型のアルゴリズムが再帰関数によって自然に与えられるのと同様に、相互再帰データ構造のアルゴリズムも相互再帰関数によって自然に与えられます。一般的な例としては、ツリーのアルゴリズムや再帰下降パーサなどがあります。直接再帰と同様に、マルチタスクに相互再帰を使用する場合など、再帰の深さが大きいか無制限である場合は、末尾呼び出しの最適化が必要です。一般的な末尾呼び出しの最適化 (末尾再帰呼び出しのように、呼び出される関数が元の関数と同じでない場合) は、末尾再帰呼び出しの最適化の特殊なケースよりも実装が難しい場合があり、そのため、末尾再帰呼び出しのみを最適化する言語では相互末尾再帰の効率的な実装が欠落している可能性があることに注意してください。使用前に宣言を必要とするPascalなどの言語では、相互再帰関数を定義するときに前方参照を避けることができないため、前方宣言が必要です。

直接再帰関数と同様に、相互再帰関数がサポートされている場合は、そのスコープ内でネストされた関数として定義されたラッパー関数が役立つ場合があります。これは、関数間でパラメータを渡すことなく、関数セット間で状態を共有する場合に特に便利です。

相互再帰の標準的な例は、明らかに人工的なものであるが、互いに呼び出してそのたびに1ずつ減算する2つの別々の関数を定義することで、負でない数が偶数か奇数かを決定する。^[3] Cの場合：

bool is_even ( unsigned int n ) { if ( n == 0 )の場合はtrueを返し、そうでない場合はis_odd ( n - 1 )を返します。 }    
       
         
    
           


bool is_odd ( unsigned int n ) { if ( n == 0 ) return false ; else return is_even ( n - 1 ); }    
       
         
    
           

これらの関数は、「 4 は偶数ですか?」という質問は「3 は奇数ですか?」と等しく、これはさらに「2 は偶数ですか?」と等しく、以下同様に 0 まで続くという観察に基づいています。この例は相互単一再帰であり、簡単に反復処理に置き換えることができます。この例では、相互再帰呼び出しは末尾呼び出しであり、一定のスタック領域で実行するには末尾呼び出しの最適化が必要になります。C では、呼び出しの代わりにジャンプを使用するように書き直さない限り、これはO ( n ) のスタック領域を占有します。 ^[4]これは単一の再帰関数 に縮小できますis_even。その場合、is_oddインライン化できる は を呼び出しますis_evenが、is_even自分自身のみを呼び出します。

より一般的な例として、ツリー上のアルゴリズムは、値に対する動作と子に対する動作に分解でき、相互に再帰する 2 つの関数に分割できます。1 つはツリー上の動作を指定して子のフォレストの forest 関数を呼び出し、もう 1 つはフォレスト上の動作を指定してフォレスト内のツリーの tree 関数を呼び出します。Python では次のようになります。

def  f_tree ( tree )  ->  None : 
    f_value ( tree . value ) 
    f_forest ( tree . children )

def  f_forest ( forest )  ->  None : 
    forest内のtreeの場合 : f_tree ( tree )  
        

この場合、ツリー関数は単一の再帰によってフォレスト関数を呼び出しますが、フォレスト関数は複数の再帰によってツリー関数を呼び出します。

上記の標準MLデータ型を使用すると、ツリーのサイズ（ノード数）は次の相互再帰関数を介して計算できます。^[5]

fun  size_tree 空 =  0 
  |  size_tree  ( Node  (_,  f ))  =  1  +  size_forest  f
および size_forest  Nil  =  0 
  |  size_forest  ( Cons  ( t ,  f' ))  =  size_tree  t  +  size_forest  f'

Schemeでのより詳細な例として、木の葉を数える例を挙げる。^[6]

( define ( count-leaves tree ) ( if ( leaf? tree ) 1 ( count-leaves-in-forest ( children tree ))))  
    
      
        

( define ( count-leaves-in-forest forest ) ( if ( null? forest ) 0 ( + ( count-leaves ( car forest )) ( count-leaves-in-forest ( cdr forest )))))  
    
      
         
           

これらの例は、フォレスト関数をツリー関数にインライン化することで、簡単に単一の再帰関数に縮小されます。これは、実際にはよく行われることです。ツリーを操作する直接再帰関数は、ノードの値を順番に処理し、子に対して再帰を 2 つの別々の関数に分割するのではなく、1 つの関数内で行います。

より複雑な例としては、再帰下降パーサーが挙げられます。これは、文法の各生成規則ごとに 1 つの関数を用意し、相互に再帰させることで自然に実装できます。生成規則は一般に複数の部分を組み合わせるため、これは一般に多重再帰になります。これは相互再帰なしでも実行できます。たとえば、各生成規則に個別の関数を用意しながら、それらを単一のコントローラー関数で呼び出すか、すべての文法を単一の関数にまとめます。

相互再帰は、各状態に 1 つの関数を持ち、状態を変更する際に単一の再帰を実行する有限状態マシンを実装することもできます。この場合、状態変更の数が多いか無制限である場合は、末尾呼び出しの最適化が必要になります。これは、協調型マルチタスクの単純な形式として使用できます。マルチタスクに対する同様のアプローチは、代わりに、互いを呼び出すコルーチンを使用することです。この場合、別のルーチンを呼び出して終了するのではなく、1 つのコルーチンが別のコルーチンに譲りますが、終了せず、譲り戻されたときに実行を再開します。これにより、個々のコルーチンが状態を保持でき、パラメータで渡したり共有変数に格納したりする必要がなくなります。

また、ミニマックス(最小と最大)などの自然に 2 つのフェーズを持つアルゴリズムもいくつかあります。これらのアルゴリズムは、相互再帰を使用して各フェーズを個別の関数にすることで実装できますが、直接再帰を使用して 1 つの関数に組み合わせることもできます。

数学において、ホフスタッターの女性シーケンスと男性シーケンスは、相互に再帰的に定義された整数シーケンスのペアの例です。

フラクタルは、再帰関数によって（指定された解像度まで）計算できます。これは、相互再帰関数を介してよりエレガントに実行できる場合があります。シェルピンスキー曲線は良い例です。

相互再帰は関数型プログラミングでは非常に一般的であり、LISP、Scheme、ML、および同様のプログラミング言語で書かれたプログラムでよく使用されます。たとえば、AbelsonとSussmanは、メタ循環評価器を使用してeval-applyサイクルでLISPを実装する方法を説明しています。^[7] Prologなどの言語では、相互再帰はほぼ避けられません。

いくつかのプログラミングスタイルでは、相互再帰を推奨していません。これは、答えを返す条件と、答えを生成せずにコードを永遠に実行し続ける条件を区別することが混乱を招く可能性があると主張しています。ピーター・ノーヴィグは、相互再帰の使用を完全に推奨しない設計パターンを指摘し、次のように述べています。 ^[8]

相互に再帰的な関数が 2 つあり、どちらもオブジェクトの状態を変更する場合は、ほぼすべての機能を 1 つの関数に移動するようにしてください。そうしないと、コードが重複してしまう可能性があります。

相互再帰は、単一の関数が直接自分自身を呼び出す直接再帰とは対照的に、間接再帰とも呼ばれます。これは単に強調点の違いであり、異なる概念ではありません。「間接再帰」は個々の関数を強調しますが、「相互再帰」は関数のセットを強調し、個々の関数を区別しません。たとえば、 f が自分自身を呼び出す場合、それは直接再帰です。代わりにf がg を呼び出し、次にg がfを呼び出し、f が再びg を呼び出す場合、 fのみの観点からはfは間接再帰であり、 gのみの観点からはg は間接再帰であり、両者の観点からはfとg は相互に再帰しています。同様に、互いに呼び出す 3 つ以上の関数のセットは、相互再帰関数のセットと呼ぶことができます。

数学的には、相互再帰関数の集合は原始再帰的であり、これは値の過程再帰によって証明でき、個々の再帰関数の値を順番にリストする単一の関数Fを構築し、相互再帰を原始再帰として書き直すことができます。 ${\displaystyle F=f_{1}(0),f_{2}(0),f_{1}(1),f_{2}(1),\dots ,}$

2 つのプロシージャ間の相互再帰は、一方のプロシージャのコードをもう一方のプロシージャにインライン化することで直接再帰に変換できます。^[9]一方のプロシージャがもう一方のプロシージャを呼び出す場所が 1 つだけであれば、これは簡単ですが、複数ある場合はコードの重複が発生する可能性があります。呼び出しスタックに関しては、2 つの相互再帰プロシージャはスタック ABABAB... を生成し、B を A にインライン化すると直接再帰 (AB)(AB)(AB)... が生成されます。

あるいは、任意の数の手続きを、手続きの選択とその引数を表すバリアント レコード(または代数データ型) を引数として受け取る単一の手続きにマージすることもできます。マージされた手続きは、対応するコードを実行するために引数をディスパッチし、直接再帰を使用して必要に応じて自分自身を呼び出します。これは、非機能化の限定的な応用と見なすことができます。^[10]この変換は、相互に再帰的な手続きのいずれかが外部コードから呼び出される可能性があり、1 つの手続きを他の手続きにインライン化する明らかなケースがない場合に役立ちます。そのようなコードは、説明したように引数をバリアント レコードにバンドルすることによって手続き呼び出しが実行されるように変更する必要があります。または、このタスクにラッパー手続きを使用することもできます。

• サイクル検出（グラフ理論）
• 再帰（コンピュータサイエンス）
• 循環依存

• ハーパー、ロバート(2000)、標準 ML でのプログラミング
• ハーヴェイ、ブライアン、ライト、マシュー (1999)。Simply Scheme: コンピュータサイエンス入門。MIT 出版。ISBN 978-0-26208281-5。
• ハットン、グラハム (2007)。Haskellによるプログラミング。ケンブリッジ大学出版局。ISBN 978-0-52169269-4。

• Rosetta Codeでの相互再帰
• 「相互再帰の適切な使用例」、「相互再帰の例はありますか？」、Stack Overflow