CODEWITHSUNDEEP
pythonpython-3.xfunctionrecursioncollatz
Harris2018
Harris2018

Reputation: 513

recursive function python 3 'maximum recursion depth exceeded'

I am creating a collatz sequence with a recursive function below:

def collatz(n):
  if n%2 == 0:
    return int(n/2)
  else:   
    return int((3 * n)/2)

From what I understand, a recursive function is a function that basically calls itself. Below I have attempted creating the recursive function with the following:

def collatz(x):
    if x == 1:
        "Done"
    print(x)
    x = collatz(x)
    return(x)

Where essentially the variable x continues to get passed into the collatz function I defined until it gets to 1. However, every time I run the recursive function it prints 'x' repeatedly and then I get the

collatz(3)    
'RecursionError: maximum recursion depth exceeded in comparison'

Which I understand is an infinite loop essentially. I thought by reassigning it to x to the results of the first collatz() it would return the new value and continue till it hit '1' but I can't seem to quite get there.

Any help/tips/advice would be great! Thanks!

Upvotes: 1

Views: 1397

Answers (3)

Adam Smith
Adam Smith

Reputation: 54223

Recursive functions have what's known as a "base case" and what's known as a "recursive case." The base case is when you should stop recursing and return an answer.

In this case, the base case is when x==1

def collatz(x):
    if x == 1:
        return x

and the recursive case is the rest of the time

# continuing from above
    else:
        if n % 2 == 0:
            return collatz(int(n//2))
        else:
            return collatz(n*3 / 2)  # sicut. Note that the collatz sequence
                                     # uses 3n+1 here, not 3n/2 as in the question

N.B. that I change the effective value of x in the next loop through collatz before returning the result of that new call. If you don't, and simply return collatz(x), you'll never reach your base case and recurse forever.

Upvotes: 3

Harris2018
Harris2018

Reputation: 513

@Roee Gavirel

Here is the final answer based on his answer above:

def collatz(x):
    if x == 1:
        "Done"
    elif x%2 == 0:
        x = int(x/2)
        print(x)
        collatz(x)     
    else:
        x = int((3*x)+1)
        print(x)
        collatz(x)


collatz(3)

Thanks for all the help!

Upvotes: 1

Roee Gavirel
Roee Gavirel

Reputation: 19453

You show two different implementations of the same function collatz, while you need to combine them.

def collatz(n):
    if x == 1:
        "Done"
    print(x)
    if n%2 == 0:
        collatz(int(n/2))
    else:   
        collatz(int((3 * n)/2))

Upvotes: 0

Related Questions