Sayed Ahmad - 7 months ago 23

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)

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
```