这些具体函数如何从使用递归转换为使用迭代？

Question

我一直致力于将库从 C 移植到 CUDA。我需要移植的两个函数都利用了递归，而 CUDA 似乎并不能很好地处理递归。因此，我想将这些函数从使用递归方法转换为迭代方法，因为即使递归确实有效，我怀疑让这些函数迭代而不是递归会更有效。

不过，我遇到了很多麻烦，因为函数使用递归的方式与传统的递归迭代问题有很大不同。

int get_resulting_node(const uint64_t np[6], const BiomeTree *bt, int idx,
    int alt, uint64_t ds, int depth)
{
    if (bt->steps[depth] == 0)
        return idx;
    uint32_t step;
    do
    {
        step = bt->steps[depth];
        depth++;
    }
    while (idx+step >= bt->len);

    uint64_t node = bt->nodes[idx];
    uint16_t inner = node >> 48;

    int leaf = alt;
    uint32_t i, n;

    for (i = 0, n = bt->order; i < n; i++)
    {
        uint64_t ds_inner = get_np_dist(np, bt, inner);
        if (ds_inner < ds)
        {
            int leaf2 = get_resulting_node(np, bt, inner, leaf, ds, depth);
            uint64_t ds_leaf2;
            if (inner == leaf2)
                ds_leaf2 = ds_inner;
            else
                ds_leaf2 = get_np_dist(np, bt, leaf2);
            if (ds_leaf2 < ds)
            {
                ds = ds_leaf2;
                leaf = leaf2;
            }
        }

        inner += step;
        if (inner >= bt->len)
            break;
    }

    return leaf;
}

和

float getSpline(const Spline *sp, const float *vals)
{
    if (!sp || sp->len <= 0 || sp->len >= 12)
    {
        printf("getSpline(): bad parameters\n");
        exit(1);
    }

    if (sp->len == 1)
        return ((FixSpline*)sp)->val;

    float f = vals[sp->typ];
    int i;

    for (i = 0; i < sp->len; i++)
        if (sp->loc[i] >= f)
            break;
    if (i == 0 || i == sp->len)
    {
        if (i) i--;
        float v = getSpline(sp->val[i], vals);
        return v + sp->der[i] * (f - sp->loc[i]);
    }
    const Spline *sp1 = sp->val[i-1];
    const Spline *sp2 = sp->val[i];
    float g = sp->loc[i-1];
    float h = sp->loc[i];
    float k = (f - g) / (h - g);
    float l = sp->der[i-1];
    float m = sp->der[i];
    float n = getSpline(sp1, vals);
    float o = getSpline(sp2, vals);
    float p = l * (h - g) - (o - n);
    float q = -m * (h - g) + (o - n);
    float r = lerp(k, n, o) + k * (1.0F - k) * lerp(k, p, q);
    return r;
}

令我困惑的是，两者都没有使用尾递归。虽然我确信这是正确的方法，但我真的很难了解如何在这里应用堆栈。

Answer 1

思考如何在汇编中实现调用抽象的函数会很有帮助。

当进行函数调用时，会在内存中分配一个新的堆栈帧，并且堆栈指针也会相应递增。当函数返回时，帧从堆栈中弹出，堆栈指针递减。

您可以通过创建一个

Stack

对象（如果您提前知道最大递归深度，它可以是一个静态分配的数组）来在 C 中“模拟”这一点。或者您可以实现类似于向量的东西并动态重新分配堆栈数组）与

StackFrame

元素。后者是一个结构体，它捕获执行函数所需的所有状态，直到下一个递归函数调用或返回语句。它不仅需要包含它可以看起来像这样

struct StackFrame {
  const uint64_t np[6];
  const BiomeTree *bt; 
  int idx;
  int alt; 
  uint64_t ds;
  int depth;

  // you should use an enum instead of separate bools
  bool function_start;
  bool after_for_loop;
  size_t inner_loop_idx; // which step of the main for loop 
  // anything else to capture the state 
};

您还需要单独跟踪最新的返回值。

现在函数的主体应该看起来像这样

// Create the first StackFrame
StackFrame first_frame = { .function_start = true; //etc.. };
stack_push(&frames, first_frame);

// Return values from all function calls are saved in this variable
int return_value; 

// "Run the simulation" 
while (!stack_empty(&stack)) {
   StackFrame current_frame = stack_last(&stack);

   // execute the appropriate portion of get_restuling_node based on the state captured in the stack frame. Either 
    if current_frame.function_start {
      //...
    }
    else if current_frame.after_for_loop {
      //...
      // return_value = ...;
      stack_pop(&stack);
    }
    else {
      // execute current_frame.inner_loop_idx th step of the for loop
      // use return_value to fetch the value of leaf2
      // finish the loop step 
      // current_frame.inner_loop_idx += 1;
      // stack_push(new_frame)
    }
}
return return_value;