1. ホーム
  2. recursion

[解決済み] 再帰とループの比較

2022-03-08 05:49:41

質問

再帰とループの両方が自然に解決できるような問題に直面しています。このような場合、規約や好ましい方法などはあるのでしょうか?(もちろん、以下のような単純なものではありません。)

再帰

Item Search(string desired, Scope scope) {
    foreach(Item item in scope.items)
        if(item.name == desired)
            return item;

    return scope.Parent ? Search(desired, scope.Parent) : null;
}

ループ

Item Search(string desired, Scope scope) {
    for(Scope cur = scope; cur != null; cur = cur.Parent)
        foreach(Item item in cur.items)
            if(item.name == desired)
                return item;

    return null;
}

解決方法は?

私は次のような場合、再帰的な解決策を好みます。

  • 再帰の実装が反復の解決策よりもはるかに単純である。通常、反復のアプローチでは不可能な方法で問題の構造的側面を利用するためである。

  • 再帰の深さがスタックオーバーフローを引き起こさないことは、この方法で再帰を実装している言語について話していると仮定すれば、合理的に保証されます。

条件1は、ここでは当てはまらないようです。反復解法も同じ程度の複雑さなので、私なら反復解法のほうに軍配を上げます。