Recursiont 1.0.0

Recursion't

Recursion't 是一个 C# 库，允许高效地实现递归算法而无需担心栈溢出。它通过创意性地使用 async 方法构建器来实现这一点。

特性

• 轻量级 如果函数中的递归不会太深，Recursion't 不会分配。
• 单线程 处理无限递归的常见方法是将递归保持在不同的线程中。Recursion't 完全在一个线程中运行。
• 内存高效 Recursion't 使用对象池等技术来保持稳态内存分配低。

使用方法

您可以通过以下步骤将递归函数转换为使用 Recursion't：

1. 在您的代码中添加 using Recursiont;。
2. 使函数为 async。
3. 如果函数返回 void，请将其返回类型更改为 RecursiveOp；如果返回 T，则更改为 RecursiveOp<T>。
4. 等待递归调用。
5. 创建一个辅助函数，使用 RecursiveRunner.Run，作为递归函数的入口点。

要查看示例，想象以下以下递归函数，该函数计算 Ackermann 函数

static uint Ackermann(uint m, uint n)
{
    if (m == 0)
    {
        return n + 1;
    }
    if (n == 0)
    {
        return Ackermann(m - 1, 1);
    }
    return Ackermann(m - 1, Ackermann(m, n - 1));
}

如果调用Ackermann(4, 1)，你的代码将会因堆栈溢出而崩溃。以下是使用递归重新编写的相同函数。

using Recursiont;

static uint Ackermann(uint m, uint n)
{
    return RecursiveRunner.Run(AckermannImpl, m, n);

    static async RecursiveOp<uint> AckermannImpl(uint m, uint n)
    {
        if (m == 0)
        {
            return n + 1;
        }
        if (n == 0)
        {
            return await AckermannImpl(m - 1, 1);
        }
        return await AckermannImpl(m - 1, await AckermannImpl(m, n - 1));
    }
}

现在，调用Ackermann(4, 1)不会导致堆栈溢出，但仍将花费异常多的时间才能完成。

RecursiveRunner.Run有接受最多六个参数的函数重载。如果你的函数参数更多，你可以创建一个接受元组的lambda

RecursiveRunner.Run(static ((int X1, int X2, int X3, int X4, int X5, int X6, int X7) x) =>
    F(x.X1, x.X2, x.X3, x.X4, x.X5, x.X6, x.X7), (0, 0, 0, 0, 0, 0, 0));

static async RecursiveOp F(int x1, int x2, int x3, int x4, int x5, int x6, int x7)
{
    // ...
}

规则

使用Recursion't伴随一系列简单的规则，你必须遵守。

术语“递归函数”指返回RecursiveOp或RecursiveOp<T>的方法。

• **紧随递归函数调用后立即使用await**。Recursion't不是协程库。以下代码可能会失败或产生意外的结果

```csharp
static async RecursiveOp Foo()
{
    RecursiveOp op1 = Bar();
    RecursiveOp op2 = Bar();
    await op1;
    await op2;
}
```

• **不要在非递归函数中调用递归函数**。从非递归函数调用递归函数的唯一方法是在RecursiveRunner.Run中传递委托。考虑以下代码

```csharp
// ❌ Wrong
F();
// ✅ Correct
RecursiveRunner.Run(F);

static async RecursiveOp F()
{
    // ...
}
```

• **在递归函数中使用RecursiveRunner.Run时要小心**。假设你有以下两个函数

```csharp
static void A()
{
    RecursiveRunner.Run(AImpl);

    static async RecursiveOp AImpl()
    {
        // ...
    }
}

static void B()
{
    RecursiveRunner.Run(BImpl);

    static async RecursiveOp BImpl()
    {
        // ...
        A();
        // ...
    }
}
```

`B` is inefficient and -if `A` and `B` are mutually recursive- downright dangerous and prone to stack overflows. The way Recursion't avoids stack overflows is by storing the stack to the heap when it goes too deep, up to the last point where `RecursiveRunner.Run` was called. Using it in recursive functions limits how many stack frames can be moved to the heap.

What you can do is to make `A()` directly return `RecursiveOp` and call and `await` it from B.

```csharp
static async RecursiveOp A()
{
    // ...
}

static void B()
{
    RecursiveRunner.Run(BImpl);

    static async RecursiveOp BImpl()
    {
        // ...
        await A();
        // ...
    }
}
```

> Unless you are doing things like recursive user callbacks, you don't have to expose recursive functions in a public API. You can create a public wrapper function that calls `RecursiveRunner.Run` and keep Recursion't as an implementation detail.

维护者

• @teo-tsirpanis