CODEWITHSUNDEEP
pythonrecursion
jyjyjyjyjyjjyjyj
jyjyjyjyjyjjyjyj

Reputation: 59

double recursion - RuntimeError: maximum recursion depth exceeded error

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 ?

Upvotes: 1

Views: 41

Answers (1)

Nathan
Nathan

Reputation: 3648

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.

Upvotes: 1

Related Questions