Here's my version of solution. It's stack safe and doesn't utilize thread pool but has specific limitation. In particular it requires tail-recursive style of method, so constructions like Fib(n-1) + Fib(n-2) won't work. From other hand the tail recursive nature which actually is executed in iterative manner doesn't require a memoization as each iteration is called once. It has no edge cases protection but it's rather a prototype than a final solution:
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);
}
And the usage:
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);
}
}
Note that it's important to return a function which wraps the recurrent call, not a call itself in order to avoid real recursion.
UPDATE
Below is another implementation which still doesn't utilize CPS transform but allows to use semantic close to algebraic recursion, that is it supports multiple recursive-like calls inside a function and doesn't require function to be tail-recursive.
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;
}
}
}
The usage:
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));
}
}
As benefits, it's stack-safe, doesn't use thread pool, isn't burdened with async await infrastructure, uses memoization and allows to use more or less readable semantic. Current implementation implies using only with functions with a single argument. To make it applicable to wider range of functions, similar implementations should be provided for different sets of generic arguments:
RecursiveTask<T1, T2, T3>
RecursiveTask<T1, T2, T3, T4>
...
IEnumerable<T>/IEnumerator<T>coupled withyieldgive you what you need? It is effectively the decoupled machinery of async/await. – PecosIEnumerator<T>is conceptually similar toMaybe[(T, IEnumerator<T>)]albeit stateful. I also mentionned a monad constructionWhile<X> = Either<X, While<X>>that does the trick, but really my question is about hijacking the CPS transform performed by the compiler on the async/await statements. – Sheathasyncsemantic doesn't imply it. – CryoscopeAwait task1.OnCoroutine(crm1)– Sheath