Function not breaking out on encountering return

Question

int min_steps(int target, int move)
{
    int x,y,z;
    cout<<target<<" "<<move<<endl;
    if(target==move || target+move==0)
    {
        return 1;
    }
   
    x = 1 + min_steps(target-move,move+1);
    y = 1 + min_steps(target+move,move+1);
    z = x<y?x:y;

    return z;    
}


int main() {
    cout<<min_steps(3,1);
    return 0;
}

In the above recursive function min_steps, the cout statement has been included to track the recursive calls. Now min_steps(3,1) encounters a call where target=2 & move=2, in which case the if condition holds True & therefore the function is supposed to return 1 & break. But this is not happening. The function is continuing to make calls and thus resulting in Time limit exceeded error

`target-move || target+move==0` does not mean what you think it means. It's equivalent to writing `(target-move != 0) || (target+move==0)` — Brian61354270, Jun 06 '21 at 15:30
Why do you think the `if` condition holds `true` when `target` is `2` and `move` is `2`? `2 - 2` is `0` which when converted to `bool` is `false`, and `2 + 2 == 0` is also `false`, and `false || false` is `false`. — Nathan Pierson, Jun 06 '21 at 15:30
`if (target - move || target + move == 0)` is equivalent to `if (target - move != 0 || target + move == 0)`. Could be a typo, but in any case, that looks like a problem. — Pete Becker, Jun 06 '21 at 15:31
@Brian @Nathan Pierson My apologies, yes I understand what you are saying. But the question did not terminate even with ```if(target==move || target+move==0)```. (I originally intended to post this, edited the question now). — nesara sr, Jun 06 '21 at 15:33
So, `min_steps(3, 1)` has to call `min_steps(2, 2)` _and_ `min_steps(4, 2)`. Is it possible the infinite descent is occurring during the evaluation of `min_steps(4, 2)`? — Nathan Pierson, Jun 06 '21 at 15:35
@NathanPierson Oh that makes sense, I realize the problem now. Thank you! — nesara sr, Jun 06 '21 at 15:38

score 0 · Answer 1 · answered Jun 06 '21 at 15:43

The problem lies in these two lines:

x = 1 + min_steps(target-move,move+1);
y = 1 + min_steps(target+move,move+1);

While as you said, the first line did return, the second line doesn't return at all. It would keep calling (4,2) -> (5,3) -> ... and cause a stack overflow error (0xC00000FD), unless in your input the if statement is already satisfied.

So to fix this you need to add more condition or change the second line probably.

Function not breaking out on encountering return

1 Answers1