Sayed Ahmad Sayed Ahmad - 6 months ago 11
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)

Answer

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

Follow up question:

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
Comments