Sayed Ahmad - 2 years ago 229
Python Question

# Nested recursive function in python

I tried to implement a nested recursive function in python it is giving an error "RuntimeError: maximum recursion depth exceeded" you can see the function in the following code. your help regarding the question is appreciated.

``````n=10

def test(n):
if n<=0:
return 1
else:
return test(test(n-1)+1)

print test(n)
``````

One very important part of recursion is that with every recursive call you have to get closer to your anchor case, which in this case is:

``````if n<=0:
return 1
``````

However, with your code you are not getting close to this case. The problem is this line:

``````return test(test(n-1)+1)
``````

Since test returns `1` when it reaches the end case and you add 1 to this result, let's see what happens when we call `test(2)`:

The anchor case isn't executed and you go straight into the `else`. The you return

``````test(test(1)+1)
``````

since `2-1=1`. Your inner test call is also going to go to the `else` case and call:

``````test(test(0)+1)
``````

Here your inner test call returns 1 (it has already reached the end case) which means that essentially in this line you are calling

``````test(2) //test(1+1)
``````

again. Here you can see that your recursion is never ending, hence your `maximum recursion depth exceeded error`.

Just to clarify how you could make this code (which is obviously just an example) work:

``````def test(n):
if n <= 0:
return 1
else:
return test(test(n-1)-1)    //notice the -1 instead of +1
``````

Why does changing the recursive call to test(test(n-2)) also result in infinite recursion?

Well this is basically because of the same reason that I pointed out right at the beginning. You need to get closer to your anchor case. While you can reach the case of `n<=0` inside the nested recursive call `test(n-2)` you can certainly not reach it inside the outer function call.

Note that your function returns 1 when it reaches it's end case, so even if `test(n-2)` doesn't cause any more recursions it returns 1 (not 0), which means you end up with

``````test(1)
``````

which is again going to cause an infinite loop (since you can not get n to be `<= 0` for this outer function call).

You have multiple options to make the recursion work for this case: By changing your return value or by changing your anchor case. So changing the if statement to either of these will prevent an infinite recursion:

``````if n <= 0:
return 0
``````

or

``````if n <= 1:
return 1    //you could also return any other value <= 1
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download