Why is this an infinite recursion?

Question

I wrote the following function to find out the number of paths we can reach from the start cell (0,0) to the destination cell (n,n). I cannot, for the life of me, figure out why this is infinite recursion.

Code is as follows:

#include <iostream>

using namespace std;

int numOfPathsToDestUtil(int start, int end, int noOfPaths, int n) {
  cout<<"Start: "<<start<<" and end: "<<end<<"and n: "<<n<<"\n";
  if(start==end && start==n)
    return noOfPaths;

  if(end<start)
    return 0;

  numOfPathsToDestUtil(start+1, end, noOfPaths+1,n) + numOfPathsToDestUtil(start, end+1, noOfPaths+1,n);
}

int numOfPathsToDest( int n ) 
{
  cout<<"n is: "<<n<<"\n";
  return numOfPathsToDestUtil(0,0,0,n);
}

int main() {
  int ans = numOfPathsToDest(4);
  cout<<ans;

  return 0;
}

Note: I am not requesting help with the code (saying so, because conditions like end<start are implementation-specific. Request you to let me understand why this recursion does not stop:

n is: 4
Start: 0 and end: 0and n: 4
Start: 1 and end: 0and n: 4
Start: 0 and end: 1and n: 4
Start: 1 and end: 1and n: 4
Start: 2 and end: 1and n: 4
Start: 1 and end: 2and n: 4
Start: 2 and end: 2and n: 4
Start: 3 and end: 2and n: 4
Start: 2 and end: 3and n: 4
Start: 3 and end: 3and n: 4
Start: 4 and end: 3and n: 4
Start: 3 and end: 4and n: 4
Start: 4 and end: 4and n: 4 --> I expect it to stop here as start=end and start=n
Start: 3 and end: 5and n: 4
Start: 4 and end: 5and n: 4
Start: 5 and end: 5and n: 4
Start: 6 and end: 5and n: 4
Start: 5 and end: 6and n: 4
Start: 6 and end: 6and n: 4

Thank you so much!

@user4581301, yes I am trying to learn using a debugger as well side-by-side. — , Jul 14 '17 at 01:16
Or maybe not even that ,much work. `numOfPathsToDestUtil` is missing a return statement. — user4581301, Jul 14 '17 at 01:16
It does have two return statements (and as seen in the output, they are reached _always_). — , Jul 14 '17 at 01:17
If they are reached always why do you have a recursive call after them? — user4581301, Jul 14 '17 at 01:18
And using a return statement as well doesn't help. `:(` I already tried it. — , Jul 14 '17 at 01:18
@user4581301, I mean, always reached for the program to stop - they are the base cases. That is why I don't expect this to be infinite. — , Jul 14 '17 at 01:19
Okay, but that doesn't help either. Still infinite: http://ideone.com/RicviH — , Jul 14 '17 at 01:19
The problem is that you have two recursive calls. The place you marked is where one of them reached the base case, but the other one never does. — Barmar, Jul 14 '17 at 01:20
@user4581301, also what two bugs? Could you kindly elaborate? — , Jul 14 '17 at 01:20
@UmedhSinghBundela There's the bug that's causing the infinite recursion, and the bug where you're not returning the value returned by the recursive calls. — Barmar, Jul 14 '17 at 01:21
@Barmar, oh.. Interesting.. Didn't think about that. Any tips to handle it please? — , Jul 14 '17 at 01:21
The second bug is that the last line of the function should be `return numOfPathsToDestUtil(start+1, end, noOfPaths+1,n) + numOfPathsToDestUtil(start, end+1, noOfPaths+1,n);` — Barmar, Jul 14 '17 at 01:22
Not all paths of numOfPathsToDestUtil() return a value. Didn't your compiler warn about that? — drescherjm, Jul 14 '17 at 01:22
@UmedhSinghBundela Make sure that the parameters to the recusive call always get you closer to the base case. — Barmar, Jul 14 '17 at 01:23
@Barmar, yes, but even including a `return` statement there makes it infinite: http://ideone.com/RicviH. And I don't fully understand, why are return there? — , Jul 14 '17 at 01:23
A function must always return or it is ill-formed. Weird things will happen. — user4581301, Jul 14 '17 at 01:24
If you don't put a return there, then you do the addition but you never pass the result back to the caller. See https://stackoverflow.com/questions/27691547/recursive-function-does-not-return-specified-value — Barmar, Jul 14 '17 at 01:24
@Barmar: _Make sure that the parameters to the recusive call always get you closer to the base case._ - could you please elaborate, sir? — , Jul 14 '17 at 01:24
@UmedhSinghBundela Actually, in graph walking like this, what you have to do is make sure you don't visit a node that you've already been to before, because then you'll keep repeating the path out of that node. So you need to make a list of all the nodes you've been to, and return if you ever get to one of them again. — Barmar, Jul 14 '17 at 01:26
@Barmar, yes, that makes sense. But then isn't doing a `+1` to the `start` and `end` variables taking me closer to the base case (my first check)? And also, as in the output I am only incrementing the values of `start` and `end` so not visiting the nodes again and again. — , Jul 14 '17 at 01:27
@UmedhSinghBundela Think of recursive factorial. Each recursive call subtracts 1, getting you closer to 0, which is the base case where the recursion stops. — Barmar, Jul 14 '17 at 01:27
`start+1` gets you closer to the base case, which is `start > end`. But `end+1` takes you further away, because `end` stays higher than `start`. — Barmar, Jul 14 '17 at 01:29
@Barmar, oh, so you mean `start+1` takes me towards the base case of `start==end and start=n`; but then `end+1` again makes the target move ahead resulting in an infinite loop - correct? — , Jul 14 '17 at 01:31
Look at the values printed on the lines after you thought it should stop. You can see the numbers getting higher. And they're higher than `n`, so `start == n` will never be true. — Barmar, Jul 14 '17 at 01:32

score 2 · Accepted Answer · answered Jul 14 '17 at 01:42

Let's label your calls

numOfPathsToDestUtil(0,0,0,n) # original (O)
numOfPathsToDestUtil(start+1, end, noOfPaths+1,n) # first-recursive (FR)
numOfPathsToDestUtil(start, end+1, noOfPaths+1,n) # second-recursive (SR)

Your output:

n is: 4 
Start: 0 and end: 0and n: 4        # O - numOfPathsToDestUtil(0,0,0,4)
Start: 1 and end: 0and n: 4        # FR -  numOfPathsToDestUtil(0+1,0,0,4)
Start: 0 and end: 1and n: 4        # SR - numOfPathsToDestUtil(0,0+1,0,4)
Start: 1 and end: 1and n: 4        # SR -> FR
Start: 2 and end: 1and n: 4        # SR -> FR -> FR
Start: 1 and end: 2and n: 4        # SR -> FR -> SR
Start: 2 and end: 2and n: 4        # SR -> FR -> SR -> FR
Start: 3 and end: 2and n: 4        # SR -> FR -> SR -> FR -> FR
Start: 2 and end: 3and n: 4        # SR -> FR -> SR -> FR -> SR
Start: 3 and end: 3and n: 4        # SR -> FR -> SR -> FR -> SR -> FR
Start: 4 and end: 3and n: 4        # SR -> FR -> SR -> FR -> SR -> FR -> FR
Start: 3 and end: 4and n: 4        # SR -> FR -> SR -> FR -> SR -> FR -> SR
Start: 4 and end: 4and n: 4        # SR -> FR -> SR -> FR -> SR -> FR -> SR -> FR (stops and returns value)
Start: 3 and end: 5and n: 4        # SR -> FR -> SR -> FR -> SR -> FR -> SR -> SR (never reaches where end==4 and n==4, keeps going and going)
Start: 4 and end: 5and n: 4
Start: 5 and end: 5and n: 4
Start: 6 and end: 5and n: 4
Start: 5 and end: 6and n: 4
Start: 6 and end: 6and n: 4

score 1 · Answer 2 · answered Jul 14 '17 at 01:41

How to debug: I will suggest you to draw a calling tree

You are missing return statement on this line

numOfPathsToDestUtil(start+1, end, noOfPaths+1,n) + numOfPathsToDestUtil(start, end+1, noOfPaths+1,n);
Consider numOfPathsToDestUtil(start, end+1, noOfPaths+1,n) only. Initial value (start,end) will be (0,0) then calling => (0,1) => then calling (0,2) => (0,3) =>(0,4) =>(0,5)... no termination constraint on end. This part will go into infinite loop
Now let's consider as a whole (hope below explanation is easy for you to understand)

Init(start, end,n, status)

(0,0,4,calling)
=>(1,0,4, will end)+(0,1,4,calling)
=>(1,1,4,calling)+(0,2, 4,calling)
=>(2,1,4,will end)+(1,2,4,calling)+(0,2, 4,calling)
=>(1,2,4,calling)+(0,2, 4,calling)
=>(2,2,4,calling)+(1,3,4,calling) +(0,2,4,calling)

I think you are able to derive the rest, and it shows that your recursion will not easily get out.

You need to modify your constraint to ensure what only "desired" condition will continue with recursion.

if end > n, will you continue recursion?
if start == end but start < n will continue recursion?

I will not list all. Hope it provide you a good thinking direction.

I understood. Thank you for your help! :) I wish I could accept your answer as well. — , Jul 14 '17 at 11:53

Why is this an infinite recursion?

2 Answers2