将递归函数转换为非递归函数

问题描述 投票:0回答:4

我正在尝试将递归函数转换为伪代码中的非递归解决方案。我遇到问题的原因是该方法中有两个递归调用。

任何帮助都会很棒。谢谢。

void mystery(int a, int b) {
    if (b - a > 1) {
        int mid = roundDown(a + b) / 2; 
         print mid; 
         mystery(a, mid); 
         mystery(mid + 1, b); 
     }
} 
algorithm recursion
4个回答
0
投票

将递归过程转换为迭代过程的texbook方法只是将递归调用替换为堆栈并运行“执行循环”,直到堆栈为空。

尝试以下操作:

push(0, 16);     /* Prime the stack */
call mystery;
...

void mystery {
do until stackempty() {   /* iterate until stack is empty */
  pop(a, b)               /* pop and process... */
  do while (b - a >= 1) { /* run the "current" values down... */
    int mid = roundDown(a+b)/2;
    print mid;  
    push(mid+1, b);       /* push in place of recursive call */
    b = mid;
  }
} 

原始函数有两个调用调用,所以为什么只有一个堆栈?忽略以下要求第二次递归调用,您可以轻松看到第一个递归调用(mystery(a, mid);)可以实现为一个简单的循环,其中b假定值为mid在每次迭代中-无需“记住”其他任何内容。所以把它变成一个循环然后简单地推动撤回堆栈所需的参数,添加一个外部循环来运行堆栈。完成。

[经过一些创造性的思考,可以使用堆栈将任何递归函数转换为迭代函数。


1
投票

这似乎更有趣,它将导致以递归函数特定的顺序显示从a到(b-1)的所有数字。请注意,所有“左”中点都在任何“右”中点之前打印。

void mystery (int a, int b) { 
     if (b > a) { 
         int mid = roundDown(a+b)/2; 
         print mid; 
         mystery(a, mid); 
         mystery(mid+1, b); 
     } 
 } 

例如,如果a = 0,b = 16,则输出为:8 4 2 1 0 3 6 5 7 12 10 9 11 14 13 15


0
投票

这是正在发生的事情。您有一根长杆,正在将其分成两部分。然后将这两个部分分成两部分。您可以对每个子部分执行此操作,直到该部分的长度变为1。

您将如何做?

假设您必须在中点折断杆。我们将把标记放在垃圾箱中以便进一步削减。注意:每个零件都会生成两个新零件,因此我们需要2 n框来存储子零件。

len = pow (2, b-a+1)      // +1 might not be needed
ar = int[len]             // large array will memoize my marks to cut
ar[0] = a                 // first mark
ar[1] = b                 // last mark 
start_ptr = 0             // will start from this point
end_ptr = 1               // will end to this point
new_end = end_ptr         // our end point will move for cuts

while true:                          //loop endlessly, I do not know, may there is a limit
  while start_ptr < end_ptr:         // look into bins
    i = ar[start_ptr]                //
    j = ar[start_ptr+1]              // pair-wise ends

    if j - i > 1                     // if lengthier than unit length, then add new marks
      mid = floor ( (i+j) / 2 )      // this is my mid
      print mid
      ar[++new_end] = i              // first mark   --|
      ar[++new_end] = mid - 1        // mid - 1 mark --+-- these two create one pair
      ar[++new_end] = mid + 1        // 2nd half 1st mark --|
      ar[++new_end] = j              // end mark          --+-- these two create 2nd pair 

    start_ptr = start_ptr + 2        // jump to next two ends

  if end_ptr == new_end             // if we passed to all the pairs and no new pair
    break                           // was created, we are done.
  else
    end_ptr = new_end               //else, start from sub prolem

PS:我没有尝试过此代码。这只是一个伪代码。在我看来,它应该完成这项工作。让我知道是否可以尝试。它将验证我的算法。它基本上是数组中的b树。


0
投票

此示例以递归方式拆分数字范围,直到该范围减小为单个值。输出显示数字的结构。单个值按顺序输出,但根据左侧的第一个拆分函数分组。

void split(int a, int b)
{
    int m;
    if ((b - a) < 2) {      /* if size == 1, return */
        printf(" | %2d", a);
        return;
    }
    m = (a + b) / 2;        /* else split array */
    printf("\n%2d %2d %2d", a, m, b);
    split(a, m);
    split(m, b);
} 
© www.soinside.com 2019 - 2024. All rights reserved.