开发者

Simple recursion question

Let's say we have a simple recursion like.

int x(int a){
   if(a<10)
     x(a+1);
    else
      !STOP!
    b++;
return b;
}

Globaly:

int b=0;

In main we could have something like this:

  int p=x(1);

Is there any way to stop the recursion so that the p will be 0, this means that "b++" will never be executed.

I'll be grateful if you could tell me some expresion to put instead of the !STOP!

But, I don't want anything like this, I just want to stop the recursion, like break; does in a while() loop...:

int ok=0;
  int x(int a){
       if(a<10)
         x(a+1);
        else
          ok=1;
 开发者_运维知识库     if(ok==0)
        b++;
    return b;
    }

If there's anything unclear about the question, just ask.


Why wouldn't you do this?

int x(int a){
   if(a<10) {
      x(a+1);
      b++;
   }
   return b;
}

The thing is, though, you're modifying a global in a recursive routine, which is not especially threadsafe and pretty sloppy. You're returning a value that is always ignored except by the top level caller. You're also doing something that is better off being done in a loop (but I assume that your actual case is bigger than this, or you're a student).

You can't really "break" the recursion - returning unwinds well enough. In oldey-timey C you might use setjmp/longjmp (and all its perils - in other words, DON'T), and in C++ you might use try/catch/throw, which will unwind the stack as well.


How about like this?

int x(int a){
   if(a>0 && a<10)
     x(a+1);
   b++;
   return b;
}


The only thing in C++ that will unwind the stack like that is an exception. There's also setjmp()/longjmp(), but those should never be used in a C++ program. Any other construct can at most return from the current function.


How about returning?

int x(int a){
   if(a<10)
     x(a+1);
    else
      return b;
    b++;
return b;
}

I think this looks a bit better

int x(int a){
   if(a<10)
     x(a+1);
    else
      return b;

    return ++b;
}

EDIT:

I think You could use exception mechanism to unwind the stack and get to the point of first invocation, but it's safe after entering main(). Referencing b in x, given the code:

int b = 0;
int p = x(1);

suggests that x is used for initialization of some global variable and may be executed before main(). How about using some helper function that wraps invocation of x in a try - catch block and throwing an exception in the place of |STOP|?


If you're trying to declare b in main(), and use b in x() then there's something wrong already to begin with. Instead, make b into a local variable by passing it as a parameter to x, and returning a modified version of b.

int x(int a, int b){
   if(a<10)
      return x(a+1,b+1);
    else
      return b;
}


I'm not a big fan of using an Exception for control. I don't expect you'll save many cycles by using Exceptions instead of if/return statements. You're going to have to test your boundary conditions anyway before throwing an Exception.

You can however simplify the problem a bit by changing the return type of the function.

bool x(int a){
  if(ok) //Exit early before next call up?
    return true;  
  if(a<10){
    if(x(a+1))  //Have we been told to exit early?
      return true; //Yes
    b++; //Do some work
    if(ok) //Exit early in the next call down?
      return true;  
  }
  return false; //Normal Exit
}
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜