关于递归改成循环或者堆栈实现的问题

递归 栈 C++ 循环

递归函数的大致框架如下：

void f(n)
{
       if(...){结束条件}
       else
       {
             f(n/2);
             f(n-n/2);
             m();//普通的函数
       }
}

大致就是上面那样了，自己已经琢磨了好几天了，还是改不好。有没有厉害的大神给点拨下。

11 个解决方案

#1

能来个大牛指点下吗？

#2

没人？在线等啊

#3

我不是大牛
就我看到的讲一下, 不知道对你是否有用

 void f(n) 应该改为 bool f(n), 如


bool f(n)
{
       if(!n) return false;
       else
       {
             if (!f(n/2)) return false;
             if (!f(n-n/2))  return false;
             m();//普通的函数
       }
}

#4

上面的建议是基于我猜"结束条件"跟N有关, 如果确实跟N有关, 那当"结束条件"成立时return到上一级, 在上一级的N跟"结束条件"的N是不一样的, 而你原来的程式问题就在这里

#5

void f(n)
{
       if(...){结束条件} 
       else
       {
             f(n/2);
             f(n-n/2);
             m();//普通的函数
       }
}
//该函数无返回值，楼主描述的过程是不太合理的，也就是　 f(n-n/2);　是没有机会执行的。
// f(n/2); 不停递归，满足结束条件就退出，否则直到栈满溢出也没机会执行  f(n-n/2);　及　m();
上述过程简化表示为：while(结束条件) n /=2;　

//没有返回值的递归，一般直接用迭代循环就可改写，有返回值的，需要用栈来模拟实现递归。

#6

引用 4 楼 EdmundLee 的回复:

上面的建议是基于我猜"结束条件"跟N有关, 如果确实跟N有关, 那当"结束条件"成立时return到上一级, 在上一级的N跟"结束条件"的N是不一样的, 而你原来的程式问题就在这里

对的，结束条件就是由n决定的

#7

引用 3 楼 EdmundLee 的回复:

我不是大牛
就我看到的讲一下, 不知道对你是否有用

 void f(n) 应该改为 bool f(n), 如


bool f(n)
{
       if(!n) return false;
       else
       {
             if (!f(n/2)) return false;
             if (!f(n-n/2))  return false;
             m();//普通的函数
       }
}

你这样做，不还是递归吗？我想改成循环

#8

引用 5 楼 PPower 的回复:

void f(n)
{
       if(...){结束条件} 
       else
       {
             f(n/2);
             f(n-n/2);
             m();//普通的函数
       }
}
//该函数无返回值，楼主描述的过程是不太合理的，也就是　 f(n-n/2);　是没有机会执行的。
// f(n/2); 不停递归，满足结束条件就退出，否则直到栈满溢出也没机会执行  f(n-n/2);　及　m();
上述过程简化表示为：while(结束条件) n /=2;　

//没有返回值的递归，一般直接用迭代循环就可改写，有返回值的，需要用栈来模拟实现递归。

过程是没有问题的。f(n-n/2)和m在f(n/2)执行完之后就可以执行。例如程序开始是f(5),则先执行f(2),f（2）结束之后执行f(3)，再之后m。

#9

简化描述为：
bool End(n){ do something }
void m() { do something }
void f(n)
{
       if( !End(n))
       {
             f(n/2);
             f(n-n/2);
             m();//普通的函数
       }
}
//改版的迭代算法：
void f(n)
{
int LOOP = 0 ;
int LOOPB = 0 ;
START:
  for(; !End(n);++LOOP) n/=2 ;  // f(n/2);结束
  for(int i = 0 ; i < LOOP ; ++i)   //共需要递归LOOP次
  {
for(; !End(n);++LOOPB)   //执行f(n-n/2);
        {
   n-=n/2;
   LOOP += LOOPB;　                // 叠加递归次数
   goto START :                //f(n-n/2); 递归
}
        for(int j = 0 ; j < LOOPB ; ++j) m(); ///f(n-n/2); 递归次数
  }
}
//即提取循环计算部分，计算 递归次数，然后执行。
简化后，大概是这样子吧，不需要用到栈。

#10

将：for(int j = 0 ; j < LOOPB ; ++j) m();
更改为：
++LOOPB ;
for(int j = 0 ; j < LOOPB ; ++j)
   m();
LOOPB = 0 ; 
这样计算递归次数才对。

#11

引用 9 楼 PPower 的回复:

简化描述为：
bool End(n){ do something }
void m() { do something }
void f(n)
{
       if( !End(n))
       {
             f(n/2);
             f(n-n/2);
             m();//普通的函数
       }
}
//改版的迭代算法：
void f(n)
{
int LOOP = 0 ;
int LOOPB = 0 ;
START:
  for(; !End(n);++LOOP) n/=2 ;  // f(n/2);结束
  for(int i = 0 ; i < LOOP ; ++i)   //共需要递归LOOP次
  {
for(; !End(n);++LOOPB)   //执行f(n-n/2);
        {
   n-=n/2;
   LOOP += LOOPB;　                // 叠加递归次数
   goto START :                //f(n-n/2); 递归
}
        for(int j = 0 ; j < LOOPB ; ++j) m(); ///f(n-n/2); 递归次数
  }
}
//即提取循环计算部分，计算 递归次数，然后执行。
简化后，大概是这样子吧，不需要用到栈。

虽然看不懂，但还是觉得很厉害。