1

だから私はC＃でこの再帰階乗関数を持っています。に対処するために使用していBigIntegerます。大きな整数を処理したいときに問題が発生し、関数が再帰的であるため、StackOverflow例外が発生します。簡単な解決策は、関数を再帰的にしないことです。これを回避する方法があるかどうか疑問に思っていますか？スタックに割り当てられたより多くの RAM の線に沿って考えていますか?

BigInteger Factorial(BigInteger n)
{
    return n == 1 ? 1 : n * Factorial(n - 1);
}
4

2 に答える 2

1

スタックを気にせずにC#で再帰関数を表現できるといいですね。しかし、残念ながらそれは直接には不可能であり、スタックをどれだけ大きくしても、スタック スペースが不足する状況が常に発生します。さらに、あなたのパフォーマンスはかなり恐ろしいものになるでしょう。この階乗のような末尾の再帰関数がある場合、何かを行うことができます。これにより、大きなペナルティなしで、元の再帰的な方法で関数を表現できます。

残念ながら、c# は末尾再帰呼び出しを直接サポートしていませんが、いわゆる「トランポリン」構造を使用して回避策が可能です。

例を参照してください。 com/2011/09/02/tail-recursion-in-c/

前回のブログから、スタックの問題なしで階乗を末尾再帰関数として実行できる次のコードが提供されます。

public static class TailRecursion
{
    public static T Execute<T>(Func<RecursionResult<T>> func)
    {
        do
        {
            var recursionResult = func();
            if (recursionResult.IsFinalResult)
                return recursionResult.Result;
            func = recursionResult.NextStep;
        } while (true);
    }

    public static RecursionResult<T> Return<T>(T result)
    {
        return new RecursionResult<T>(true, result, null);
    }

    public static RecursionResult<T> Next<T>(Func<RecursionResult<T>> nextStep)
    {
        return new RecursionResult<T>(false, default(T), nextStep);
    }

}

public class RecursionResult<T>
{
    private readonly bool _isFinalResult;
    private readonly T _result;
    private readonly Func<RecursionResult<T>> _nextStep;
    internal RecursionResult(bool isFinalResult, T result, Func<RecursionResult<T>> nextStep)
    {
        _isFinalResult = isFinalResult;
        _result = result;
        _nextStep = nextStep;
    }

    public bool IsFinalResult { get { return _isFinalResult; } }
    public T Result { get { return _result; } }
    public Func<RecursionResult<T>> NextStep { get { return _nextStep; } }
}

class Program
{
    static void Main(string[] args)
    {
        BigInteger result = TailRecursion.Execute(() => Factorial(50000, 1));
    }

    static RecursionResult<BigInteger> Factorial(int n, BigInteger product)
    {
        if (n < 2)
            return TailRecursion.Return(product);
        return TailRecursion.Next(() => Factorial(n - 1, n * product));
    }
}
于 2013-08-18T21:46:19.047 に答える
-1

必要なスタックサイズで新しいスレッドを作成できます...

var tcs = new TaskCompletionSource<BigInteger>();
int stackSize = 1024*1024*1024;

new Thread(() =>
    {
        tcs.SetResult(Factorial(10000));
    },stackSize)
    .Start();

var result = tcs.Task.Result;

しかし、コメントで述べたように、これには反復的な方法が適しています..

于 2013-08-18T21:34:12.343 に答える