Способ обхода размера стека

Question

Итак, у меня есть эта рекурсивная факториальная функция в C#. Я использую его для работы с BigInteger. Проблема возникает, когда я хочу иметь дело с большими целыми числами, и потому что моя функция рекурсивна, это вызовет исключение StackOverflow. Теперь простое решение состоит в том, чтобы не сделать функцию рекурсивной. Мне интересно, есть ли способ обойти это? Я думаю, что по линии больше бара выделяется стек?

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

Answer 1

Вы можете создать новую тему с STACKSIZE вы хотите ...

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

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

var result = tcs.Task.Result; 

Но, как упоминалось в комментариях, итеративный способ для этого было бы лучше ..

Answer 2

Я понимаю это хорошо, если вы могли бы выразить рекурсивные функции в 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)); 
    } 
}