Вот мой вариант решения.Это стек безопасно и не использует пул потоков, но имеет определенные ограничения.В частности, он требует хвостовой рекурсивный стиль метода, поэтому конструкции типа Fib(n-1) + Fib(n-2) не будут работать.С другой стороны, хвостовая рекурсивная природа, которая фактически выполняется итеративным образом, не требует запоминания, поскольку каждая итерация вызывается один раз.У него нет защиты крайних случаев, но это скорее прототип, чем окончательное решение:
public class RecursiveTask<T>
{
private T _result;
private Func<RecursiveTask<T>> _function;
public T Result
{
get
{
var current = this;
var last = current;
do
{
last = current;
current = current._function?.Invoke();
} while (current != null);
return last._result;
}
}
private RecursiveTask(Func<RecursiveTask<T>> function)
{
_function = function;
}
private RecursiveTask(T result)
{
_result = result;
}
public static implicit operator RecursiveTask<T>(T result)
{
return new RecursiveTask<T>(result);
}
public static RecursiveTask<T> FromFunc(Func<RecursiveTask<T>> func) => new RecursiveTask<T>(func);
}
И использование:
class Program
{
static RecursiveTask<int> Fib(int n, int a, int b)
{
if (n == 0) return a;
if (n == 1) return b;
return RecursiveTask<int>.FromFunc(() => Fib(n - 1, b, a + b));
}
static RecursiveTask<int> Factorial(int n, int a)
{
if (n == 0) return a;
return RecursiveTask<int>.FromFunc(() => Factorial(n - 1, n * a));
}
static void Main(string[] args)
{
Console.WriteLine(Factorial(5, 1).Result);
Console.WriteLine(Fib(100000, 0, 1).Result);
}
}
Обратите внимание, что важно вернуть функцию, которая оборачивает рекуррентныйвызов, а не вызов, чтобы избежать реальной рекурсии.
ОБНОВЛЕНИЕ Ниже приведена другая реализация, которая все еще не использует преобразование CPS, но позволяет использовать семантическую близость к алгебраической рекурсии, то естьон поддерживает несколько рекурсивных вызовов внутри функции и не требует, чтобы функция была хвостовой рекурсивной.
public class RecursiveTask<T1, T2>
{
private readonly Func<RecursiveTask<T1, T2>, T1, T2> _func;
private readonly Dictionary<T1, RecursiveTask<T1, T2>> _allTasks;
private readonly List<RecursiveTask<T1, T2>> _subTasks;
private readonly RecursiveTask<T1, T2> _rootTask;
private T1 _arg;
private T2 _result;
private int _runsCount;
private bool _isCompleted;
private bool _isEvaluating;
private RecursiveTask(Func<RecursiveTask<T1, T2>, T1, T2> func)
{
_func = func;
_allTasks = new Dictionary<T1, RecursiveTask<T1, T2>>();
_subTasks = new List<RecursiveTask<T1, T2>>();
_rootTask = this;
}
private RecursiveTask(Func<RecursiveTask<T1, T2>, T1, T2> func, T1 arg, RecursiveTask<T1, T2> rootTask) : this(func)
{
_arg = arg;
_rootTask = rootTask;
}
public T2 Run(T1 arg)
{
if (!_isEvaluating)
BuildTasks(arg);
if (_isEvaluating)
return EvaluateTasks(arg);
return default;
}
public static RecursiveTask<T1, T2> Create(Func<RecursiveTask<T1, T2>, T1, T2> func)
{
return new RecursiveTask<T1, T2>(func);
}
private void AddSubTask(T1 arg)
{
if (!_allTasks.TryGetValue(arg, out RecursiveTask<T1, T2> subTask))
{
subTask = new RecursiveTask<T1, T2>(_func, arg, this);
_allTasks.Add(arg, subTask);
_subTasks.Add(subTask);
}
}
private T2 Run()
{
if (!_isCompleted)
{
var runsCount = _rootTask._runsCount;
_result = _func(_rootTask, _arg);
_isCompleted = runsCount == _rootTask._runsCount;
}
return _result;
}
private void BuildTasks(T1 arg)
{
if (_runsCount++ == 0)
_arg = arg;
if (EqualityComparer<T1>.Default.Equals(_arg, arg))
{
Run();
var processed = 0;
var addedTasksCount = _subTasks.Count;
while (processed < addedTasksCount)
{
for (var i = processed; i < addedTasksCount; i++, processed++)
_subTasks[i].Run();
addedTasksCount = _subTasks.Count;
}
_isEvaluating = true;
}
else
AddSubTask(arg);
}
private T2 EvaluateTasks(T1 arg)
{
if (EqualityComparer<T1>.Default.Equals(_arg, arg))
{
foreach (var task in Enumerable.Reverse(_subTasks))
task.Run();
return Run();
}
else
{
if (_allTasks.TryGetValue(arg, out RecursiveTask<T1, T2> task))
return task._isCompleted ? task._result : task.Run();
else
return default;
}
}
}
Использование:
class Program
{
static int Fib(int num)
{
return RecursiveTask<int, int>.Create((t, n) =>
{
if (n == 0) return 0;
if (n == 1) return 1;
return t.Run(n - 1) + t.Run(n - 2);
}).Run(num);
}
static void Main(string[] args)
{
Console.WriteLine(Fib(7));
Console.WriteLine(Fib(100000));
}
}
Преимущества: он безопасен для стека, не использует пул потоков, не обременен инфраструктурой async await, используетзапоминание и позволяет использовать более или менее читабельную семантикуТекущая реализация подразумевает использование только с функциями с одним аргументом.Чтобы сделать его применимым к более широкому диапазону функций, должны быть предусмотрены аналогичные реализации для различных наборов универсальных аргументов:
RecursiveTask<T1, T2, T3>
RecursiveTask<T1, T2, T3, T4>
...