double recursion - RuntimeError: maximum recursion depth exceeded error

Question

I tried to build a function as follows:

a(0,m) = m+1
a(n+1,0) = a(n,1)
a(n+1,m+1) = a(n,a(n+1,m))

First try was :

def a(n,m):
    if n == 0:
        return m + 1
    elif m == 1:
        return a(n ,0)
    else:
        return a(n - 1, a(n, m - 1))

and I got

RuntimeError: maximum recursion depth exceeded

So the second try was this and I worked.

def a(n,m):
    if n == 0:
        return m + 1
    elif m == 0:
        return a(n-1 , 1)
    else:
        return a(n - 1, a(n, m - 1))

So the question is I don't fully understand which difference in processing two functions why the first one got max. recursion depth exceeded error and second not ?

checkout this link youtu.be/i7sm9dzFtEI. your first algo is similar to this. — Poojan
Your second base case appears to be wrong. In the case of a(1, 0) it should call a(0, 1). That is a(0+1, 0) = a(0, 1) = 1 + 1. We can see this should be caught by the first base case. But instead it goes into the recursive case -- which is the cause of your infinite recursion. — Dunes

Nathan Nathan · Accepted Answer · 2019-02-09T15:18:41

The problem occures when:

n != 0 (say: x)
m = 0

What happens?

First, n != 0, so the first if statement is skipped.

However, m=0, so the first elif statement is accepted. What is returned?

n still doesn't equal 0 (it equals x)
m still equals 0

So the exact same question is posed and the process starts over, never to end.

In your updated code you ask for n-1, so n will slowly reduce until it's 0, and the first if statement is accepted, after which the program terminates.

double recursion - RuntimeError: maximum recursion depth exceeded error

1 Answers