c# - 绕过堆栈大小的方法

Question

所以我在c#中有这个递归阶乘函数。我用它来处理BigInteger。当我想处理大整数时会出现问题，因为我的函数是递归的，所以会导致StackOverflow异常。现在简单的解决方案是不使函数递归。我想知道是否有办法解决这个问题？我在考虑分配堆栈的更多内存？

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

Answer 1

我知道如果您可以在 C# 中表达递归函数而不用担心堆栈，那就太好了。但不幸的是，这不是直接可能的，而且无论你的堆栈有多大，总会有你用完堆栈空间的情况。此外，您的表现可能会非常可怕。如果你有一个像这个阶乘这样的尾递归函数，可以做一些事情，这几乎可以让你以原始递归方式表达你的函数，而不会造成巨大的损失。

不幸的是，c# 不直接支持尾递归调用，但可以使用所谓的“蹦床”构造来解决问题。

参见例如：http ://bartdesmet.net/blogs/bart/archive/2009/11/08/jumping-the-trampoline-in-c-stack-friendly-recursion.aspx和http://www.thomaslevesque。 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));
    }
}

Answer 2

您可以使用所需的堆栈大小创建一个新线程...

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

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

var result = tcs.Task.Result;

但正如评论中提到的，一个迭代的方式会更好..