Nested recursive function in python

Question

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)

Keiwan · Accepted Answer · 2016-05-28 16:11:52Z

6

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

edited May 28, 2016 at 16:11

answered May 28, 2016 at 15:11

Keiwan

8,3115 gold badges38 silver badges49 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Sayed Ahmad Over a year ago

Keiwan Thank you very much, the answer is really helpful, if I make the last line like test(test(n-2)) it a gain goes to infinity so my question was how these nested functions call each other. if you can add a bite more.

Sayed Ahmad Over a year ago

Thank you I got it, I appreciate the way you answered :)

Collectives™ on Stack Overflow

Nested recursive function in python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related