none
关于递归的一个问题? RRS feed

  • 问题

  • 请问使用带返回值的递归函数和void递归函数哪个效率高?是不是带返回值的递归层数比void少?
    问题源于一个迷宫求解题,求迷宫中是否存在从入口到出口长度为t的路径。
    http://acm.hdu.edu.cn/showproblem.php?pid=1010

    #include <cstdio>
    #include <vector>
    #include <algorithm>
    #include <cmath>

    using namespace std;

    typedef vector< vector<char> > Map;

    //这个函数提交后超时
    //void exist_path(Map &map, int i, int j, int dx, int dy,
    //    int m, int n, int len, bool &find, int t)
    //{
    // if( i==dx && j==dy && len==t )
    // {
    //  find=true;
    //  return;
    // }
    // if( len>t || (abs(i-dx)+abs(j-dy))%2!=abs(len-t)%2 ) return;
    // map[i][j]='X';
    // if( j+1<n && map[i][j+1]!='X' )
    //  exist_path(map, i, j+1, dx, dy, m, n, len+1, find, t);
    // if( i+1<m && map[i+1][j]!='X' )
    //  exist_path(map, i+1, j, dx, dy, m, n, len+1, find, t);
    // if( j-1>=0 && map[i][j-1]!='X' )
    //  exist_path(map, i, j-1, dx, dy, m, n, len+1, find, t);
    // if( i-1>=0 && map[i-1][j]!='X' )
    //  exist_path(map, i-1, j, dx, dy, m, n, len+1, find, t);
    // map[i][j]='.';
    //}

    //这个提交后OK
    bool exist_path(Map &map, int i, int j, int dx, int dy,
        int m, int n, int len, int t)
    {
     if( i==dx && j==dy && len==t ) return true;
     if( len>t || (abs(i-dx)+abs(j-dy))%2!=abs(len-t)%2 ) return false;
     map[i][j]='X';
     if( j+1<n && map[i][j+1]!='X' && exist_path(map, i, j+1, dx, dy, m, n, len+1, t))
      return true;
     if( i+1<m && map[i+1][j]!='X' && exist_path(map, i+1, j, dx, dy, m, n, len+1, t))
      return true;
     if( j-1>=0 && map[i][j-1]!='X' && exist_path(map, i, j-1, dx, dy, m, n, len+1, t))
      return true;
     if( i-1>=0 && map[i-1][j]!='X' && exist_path(map, i-1, j, dx, dy, m, n, len+1, t))
      return true;
     map[i][j]='.';
     return false;
    }

    int main()
    {
     freopen("aaa.txt", "r", stdin);
     int m, n, t;
     while( scanf("%d%d%d", &m, &n, &t)!=EOF && m!=0 )
     {
      getchar();
      Map map(m, vector<char>(n+2, 0));
      for( int i=0; i<m; ++i )
       scanf("%s", &map[i][0]);
      int ex, ey, dx, dy;
      for( int i=0; i<m; ++i )
       for( int j=0; j<n; ++j )
        if( map[i][j]=='S')
        { ex=i; ey=j; }
        else if(map[i][j]=='D')
        { dx=i, dy=j; }
      //bool b=false;
      //exist_path(map, ex, ey, dx, dy, m, n, 0, b, t);
      bool b=exist_path(map, ex, ey, dx, dy, m, n, 0, t);
      if(b) printf("YES\n");
      else printf("NO\n");
     }
     return 0;
    }

    2010年1月20日 6:49

答案

  • 通过返回值,还是参数传回结果值,并没有本质的区别。如果效果不一样,是算法有问题。


    麻烦把正确答案设为解答。

    并非没有关系。
    Windows默认堆栈是1M的大小,有返回值的函数在调用后会把返回值push到堆栈中
    这样,很明显void的返回值要比int的少占用堆栈,所以可以进行更多的迭代而不会导致堆栈溢出。
    不过这是很极限的情况才需要考虑的,一般工程不会达到上百万次的迭代,但是进行科学计算时这是需要考虑的
    0xBAADF00D
    2010年2月6日 12:00
    版主

全部回复

  • 关键还是你两个算法不等价。 跟有没有返回值没关系。
    2010年1月20日 9:12
    版主
  • 带返回的递归返回值要多占用线程堆栈4个字节,会比void多占内存,在堆栈一定的情况下,是要比void型少一些。

    至于速度和效率,没有关系。
    0xBAADF00D
    2010年1月20日 14:48
    版主
  • 我觉得主要还是看算法,和返回值类型没多大关系。
    2010年1月21日 1:10
  • “这个函数提交后超时”是什么意思?死循环了还是程序挂掉了?
    Windows的程序的堆栈都是有限的,默认是一兆,总有用完的一天。所以,尽量不要写递归程序,它总有运行失败的时候。而且你怎么知道别人是在哪个堆栈深度调用的你的递归函数呢?
    LHL
    2010年2月2日 9:04
  • 通过返回值,还是参数传回结果值,并没有本质的区别。如果效果不一样,是算法有问题。


    麻烦把正确答案设为解答。
    2010年2月5日 1:12
    版主
  • 通过返回值,还是参数传回结果值,并没有本质的区别。如果效果不一样,是算法有问题。


    麻烦把正确答案设为解答。

    并非没有关系。
    Windows默认堆栈是1M的大小,有返回值的函数在调用后会把返回值push到堆栈中
    这样,很明显void的返回值要比int的少占用堆栈,所以可以进行更多的迭代而不会导致堆栈溢出。
    不过这是很极限的情况才需要考虑的,一般工程不会达到上百万次的迭代,但是进行科学计算时这是需要考虑的
    0xBAADF00D
    2010年2月6日 12:00
    版主