0

典型的な以外の再帰関数を設計する言語に依存しない他の方法は何ですか:

if (counter < 1) 
    return output;
else
   callSelf();

他の方法は存在しますか？例を表示するときは常に、上記のコードのバージョンが表示されます。

ありがとう！:)

4

8 に答える 8

6

それだけです。

再帰関数の設計は、「まだ値を返すことができるか、それともさらに処理を行う必要があるか」と同じくらい単純です。「処理によって値が返されました。渡す前にどうすればよいですか?」

末尾再帰は、コンパイラ/インタプリタがパフォーマンスを向上させるために使用できる最適化方法です。基本的に、再帰関数が厳密な形式に従う場合 (再帰呼び出しの後に何も起こらない場合、通常、再帰呼び出しは常に とペアになっていることを意味しますreturn)、再帰関数を最適化し、for ループとして書き直すことができます。

于 2009-10-06T18:52:54.133 に答える
5

あなたの質問は正確には何ですか？いくつかの答えを試しているだけです;-)

再帰には多くの種類があります。

  • 「標準」再帰

    let rec sum = function
    | [] -> 0
    | x::x' -> x + sum x'

  • 末尾再帰

    let rec sum acc = function
    | [] -> acc
    | x::x' -> sum (x + acc) x'

  • 相互再帰

     let rec f() = g()
 and g() = f()

  • 固定小数点再帰

    let factorial n = fix(fun rec n -> if n < 1 then 1 else n * rec (n - 1)) n

また、再帰のアプリケーションのリストは非常に豊富です。関数型プログラミングでは、反復コード (for ループなど) はすべて再帰によって表現されます。

別の良い例:

let rec sumTree = function
| End -> 0
| Node(val, right, left) = val + sumTree right + sumTree left

再帰の主な「ベストプラクティス」は、終了条件がある時点で満たされるようにすることです。そのため、通常、最初の呼び出しよりも「小さい」データで関数を自己呼び出します (ツリーの一部のみ)。 ）。それ以外の場合は、無限の再帰が発生する可能性があります。

于 2009-10-06T18:59:21.950 に答える
3

ええと、再帰をいつ停止するかを知る何らかの方法が必要です。それがあなたcounter < 1ですよね？リストからアイテムを頻繁に削除/追加し、ツリーをたどり、再帰中に数学関数を実行します。最終的には、再帰をいつ停止し、いつ停止しないかを知る必要があるため、 に要約できないオプションは他にありませんcounter < 1。

function ProcessNode(node)
  //Do stuff
  while (node.Next != null)
    ProcessNode(node.Next);

function ManipulateList(list)
  //Do stuff, adding and removing items based on logic
  if (testCondition)
    return;
  else
    ManipulateList(list);
于 2009-10-06T18:52:34.257 に答える
1

たとえば、さまざまなバリエーションがあります。

foreach (child in parameter.GetChildren()) {
   callself(child)
}

また

switch (param.length) {
   case 1: return param[0];
   case 2: return param[0] + param[1];
   default: return callself(param.FirstHalf()) + callself(param.LastHalf());
}

それらすべてに共通しているのは、タスクをより小さなタスクに分割し、それ自体を使用して、簡単な操作で解決できるほど小さくなるまで、より小さなタスクを解決することです。

于 2009-10-06T19:05:43.353 に答える
1

遅延プログラミング言語では、終点を定義しない再帰を使用できます。結果は無限のデータ構造になる可能性がありますが、すべてを使用しようとしない限り問題ありません。たとえば、Haskell でフィボナッチ数列全体を定義する一般的な方法は次のとおりです。

fibS = 1:1: zipWith (+) fibS (tail fibS)

これは次の英語に変換されます: フィボナッチ数列は 1 で、その後に 1 が続き、その後にフィボナッチ数列と最初の要素を除いたフィボナッチ数列の要素ごとの合計である数列が続きます。

これは、再帰的な関数呼び出しではなく、再帰的な定義のように聞こえますが、Haskell では大きな違いはありません。上記は単なる「nullary 関数」(引数を取らない関数) です。

通常、これを使用するには、fibS の最初の N 個の要素を使用するだけです。プログラムが永久に実行されていることに満足している限り、実際にはすべてを使用できます (たとえば、すべてを印刷する) :-)

無限再帰の「all」を使用するより有用な例として、Web サーバーには、終了しない再帰関数を使用して定義された永久に実行される「メイン ループ」がある場合があります。

編集: 「怠惰」の要素が存在する場合、これらの原則は他の言語にも適用できます。以下は、ジェネレーターを使用して Python に移植された上記の fibS の実装です。

def zipWith(func, iter1, iter2):
    while True:
        yield func(iter1.next(), iter2.next())

def tail(iter):
    iter.next()
    for x in iter:
        yield x

def fibS():
    yield 1
    yield 1
    for x in zipWith(lambda x,y: x + y, fibS(), tail(fibS())):
        yield x

# Test it by printing out the first n elements.
def take(n, iter):
    while n > 0:
        yield iter.next()
        n = n - 1

print list(take(10, fibS()))

Haskell バージョンほど効率的であるとは思わないでください。いくつかのハックとある種のグローバルオブジェクトを使用して、より効率的にすることができます。ただし、明示的な終了条件がないことに注意してください。

于 2009-10-06T19:38:36.333 に答える
0

再帰を停止したい場合は、テストを実行する必要があります。

ただし、Hanoi Tower アルゴリズム (2 回の再帰呼び出し) のように、少し異なるものを使用することもできます。

ハノイタワー

int Hanoi( source, mid, destination, height ) {

if ( height == 1 ) { print source '->' destination }
else
   Hanoi ( source, destination, mid, height - 1 ) ; # move all upper tower from source to mid
   print source '->' destination;
   Hanoi ( mid , source, destination, height -1 ) ; # move all the upper tower from mid to destination

}
Hanoi ( "0", "1", "2", 8 );

ソースから宛先に 8 つのディスクを移動するソリューションを出力します。ゲームのルールについては、http://en.wikipedia.org/wiki/Tower_of_Hanoiを参照してください。

于 2009-10-06T19:01:28.293 に答える
0

Google には、再帰に関する多くの情報があります。:)

于 2009-10-06T19:03:16.560 に答える
0

「ベスト プラクティス」は、構造誘導 (大まかに言うと、データ構造の折り畳み) を使用することです。それが失敗した場合は、一般的な (無制限の) 再帰を検討することをお勧めします。

たとえば、リストを操作する場合、折り畳みを使用するのが通例です。連結や追加などの多くの関数は、この方法で簡単に記述できます。

于 2011-01-26T15:34:55.213 に答える