递归的 goto 及 while 实现

计算机3D图像相关技术的讨论

递归的 goto 及 while 实现

帖子awakening3d » 2017年 4月 11日 18:32

函数递归调用在某些场合是不能使用的,我们可以使用 goto 或 while 来替代实现递归:

代码: 全选
#include "stdafx.h"


typedef struct {
   int a, b, c;
} param_t;

param_t p[999];
int d=0;

void push(int aa, int bb, int cc)
{
   p[d].a = aa; p[d].b = bb; p[d].c = cc;
   d++;
}

void pop(int& aa, int& bb, int& cc)
{
   d--;
   aa = p[d].a; bb = p[d].b; cc = p[d].c;
}



int fr(int n)
{
   if (n<2) return n;
   int t = fr( n-1 );
   t += fr(n-2);
   t -= fr(n-3);

   if (t<0) return t;

   t*=2;

   return t;

}

int frgoto(int n)
{
   int result = 0;
   int t = 0;

begincall:
   if (n<2) {
      result = n;
      goto endcall;
   }
   push(1, n, t);
   n = n-1;
   goto begincall;

returncall1:
   t = result;
   push(2, n, t);
   n = n-2;
   goto begincall;

returncall2:
   t += result;
   push(3, n, t);
   n = n-3;
   goto begincall;

returncall3:
   t -= result;
   if (t<0) {
      result = t;
      goto endcall;
   }
   t*=2;
   result = t;
   goto endcall;


endcall: // exit function
   if (0==d) return result;
   int a;
   pop(a,n,t);
   switch (a) {
      case 1: goto returncall1;
      case 2: goto returncall2;
      case 3: goto returncall3;
   }
}

int frwhile(int n)
{
   int result = 0;
   int t = 0;

   while (true) {
      if (n<2) {
         result = n;
         bool b = false;
         while (0!=d) { // endcall
            int a;
            pop(a,n,t);
            if (1==a) {
               t = result;
               push(2, n, t);
               n = n-2;
               b = true;
               break;
            } else if (2==a) {
               t += result;
               push(3, n, t);
               n = n-3;
               b = true;
               break;
            } else if (3==a) {
               t -= result;
               if (t<0) {
                  result = t;
                  continue;
               }
               t*=2;
               result = t;
               continue;
            }
         }
         if (b) continue; else break;
      }
      push(1, n, t );
      n = n-1;
   }
   return result;
}

int main(int argc, char* argv[])
{
   printf("Hello World!\n");
   printf("fr: %d\n", fr(20) );
   printf("frgoto: %d\n", frgoto(20) );
   printf("frwhile: %d\n", frwhile(20) );
   return 0;
}

awakening3d
网站管理员
 
帖子: 147
注册: 2010年 10月 28日 17:39

回到 学习交流

在线用户

正在浏览此版面的用户:没有注册用户 和 1 位游客