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.
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:
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
The anchor case isn't executed and you go straight into the
else. The you return
2-1=1. Your inner test call is also going to go to the
else case and call:
Here your inner test call returns 1 (it has already reached the end case) which means that essentially in this line you are calling
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
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
if n <= 1: return 1 //you could also return any other value <= 1