C# 递归函数有助于理解它是如何工作的？

Question

我需要帮助来理解函数是如何工作的；：它是一个带有yield return的递归函数，但我不知道它是如何工作的。它用于计算一组数据的累积密度函数（近似值）。
非常感谢大家。

/// Approximates the cumulative density through a recursive procedure 
/// estimating counts of regions at different resolutions.
/// </summary>
/// <param name="data">Source collection of integer values</param>
/// <param name="maximum">The largest integer in the resulting cdf (it has to be a power of 2...</param>
/// <returns>A list of counts, where entry i is the number of records less than i</returns>


public static IEnumerable<int> FUNCT(IEnumerable<int> data, int max)
  {
    if (max == 1)
        {
            yield return data.Count();
        }
        else
        {
            var t = data.Where(x => x < max / 2);
            var f = data.Where(x => x > max / 2);

            foreach (var value in FUNCT(t, max / 2))
                yield return value;  

            var count = t.Count();
            f = f.Select(x => x - max / 2);
            foreach (var value in FUNCT(f, max / 2))   
                yield return value + count;
        }
    }

Answer 1

从本质上讲，使用yield返回函数的IEnumerable函数与传统的递归函数略有不同。作为基本情况，假设您有：

IEnumerable<int> F(int n)
{
    if (n == 1)
    {
       yield return 1;
       yield return 2;
       // implied yield return break;
    }
    // Enter loop 1
    foreach (var v in F(n - 1))
        yield return v;
    // End loop 1
    int sum = 5;
    // Enter loop 2
    foreach (var v in F(n - 1))
        yield return v + sum;
    // End loop 2
    // implied yield return break;
}
void Main()
{
   foreach (var v in F(2))
       Console.Write(v);
   // implied return
}

F 采用原始 FUNCT 的基本形式。如果我们调用 F(2)，则遍历结果：

F(2)
|   F(1)
|   |   yield return 1
|   yield return 1
Console.Write(1);
|   |  yield return 2    
|   yield return 2
Console.Write(2)
|   |  RETURNS
|   sum = 5;
|   F(1)
|   |  yield return 1
|   yield return 1 + 5
Console.Write(6)
|   |  yield return 2
|   yield return 2 + 5
Console.Write(7)
|   |  RETURNS
|   RETURNS
RETURNS

并打印 1267。请注意，yield return 语句将控制权交给调用者，但下一次迭代会导致函数在先前让出的位置继续执行。

CDF 方法确实增加了一些额外的复杂性，但不多。递归将集合分成两部分，并计算每部分的 CDF，直到 max=1。然后该函数计算元素的数量并产生它，每个产生递归地传播到封闭循环。

要演练 FUNCT，假设您使用 data=[0,1,0,1,2,3,2,1] 和 max=4< 运行/代码>。然后使用与上面相同的 Main 函数作为驱动程序运行该方法，结果如下：

FUNCT([0,1,0,1,2,3,2,1], 4)
| max/2 = 2
| t = [0,1,0,1,1]
| f = [3] // (note: per my comment to the original question,
|         // should be [2,3,2] to get true CDF.  The 2s are
|         // ignored since the method uses > max/2 rather than
|         // >= max/2.)
| FUNCT(t,max/2) = FUNCT([0,1,0,1,1], 2)
| |    max/2 = 1
| |    t = [0,0]
| |    f = [] // or [1,1,1]
| |    FUNCT(t, max/2) = FUNCT([0,0], 1)
| |    |   max = 1
| |    |   yield return data.count = [0,0].count = 2
| |    yield return 2
| yield return 2
Console.Write(2)
| |    |   RETURNS
| |    count = t.count = 2
| |    F(f, max/2) = FUNCT([], 1)
| |    |   max = 1
| |    |   yield return data.count = [].count = 0
| |    yield return 0 + count = 2
| yield return 2
Console.Write(2)
| |    |   RETURNS
| |    RETURNS
| count = t.Count() = 5
| f = f - max/2 = f - 2 = [1]
| FUNCT(f, max/2) = FUNCT([1], 2)
| |    max = 2
| |    max/2 = 1
| |    t = []
| |    f = [] // or [1]
| |    FUNCT(t, max/2) = funct([], 1)
| |    |   max = 1
| |    |   yield return data.count = [].count = 0
| |    yield return 0
| yield return 0 + count = 5
Console.Write(5)
| |    |   RETURNS
| |    count = t.count = [].count = 0
| |    f = f - max/2 = []
| |    F(f, max/2) = funct([], 1)
| |    |   max = 1
| |    |   yield return data.count = [].count = 0
| |    yield return 0 + count = 0 + 0 = 0
| yield return 0 + count = 0 + 5 = 5
Console.Write(5)
| |    RETURNS
| RETURNS
RETURNS

因此返回值 (2,2,5,5)。 （使用 >= 将产生值 (2,5,7,8) - 请注意，这些是非负积分数据的缩放 CDF 的精确值，而不是近似值） 。

Answer 2

有趣的问题。假设您了解 yield 的工作原理，该函数的注释（在您的问题）非常有帮助。我按照我的理解对代码进行了评论，这可能会有所帮助：

    public static IEnumerable<int> FUNCT(IEnumerable<int> data, int max)
    {
        if (max == 1)
        {
            // Effectively the end of the recursion.
            yield return data.Count();
        }
        else
        {
            // Split the data into two sets
            var t = data.Where(x => x < max / 2);
            var f = data.Where(x => x > max / 2);

            // In the set of smaller numbers, recurse to split it again
            foreach (var value in FUNCT(t, max / 2))
                yield return value;

            // For the set of smaller numbers, get the count.
            var count = t.Count();

            // Shift the larger numbers so they are in the smaller half.
            // This allows the recursive function to reach an end.
            f = f.Select(x => x - max / 2);

            // Recurse but add the count of smaller numbers. We already know there 
            // are at least 'count' values which are less than max / 2.
            // Recurse to find out how many more there are.
            foreach (var value in FUNCT(f, max / 2))   
                yield return value + count;
        }
    }