Trying to understand recursion - Why is my function reaching maximum recursion or None?-CodePudding

This question has been asked a ton, but after looking through the posts and following what the answers say, I don't understand why my code is still not working

All of the posts on recursion say that you need to include a return statement to actually return the values, instead of None. But when i do this I get an infinite recursion. I have my base case down, along with the 2 other cases for the collatz sequence. I want it to print out the numbers, but this is an infinite recursion.

#Maximum recursion
def find_collatz_nums(number):
    if number == 1:
        return find_collatz_nums(number)
    if number % 2 == 0:
        return find_collatz_nums(number/2)
    return find_collatz_nums((3 * number)   1)

print(find_collatz_nums(3))

So then if I just try to do a blank return in the base case it will just return None. This is below.

#returns None
def find_collatz_nums(number):
    if number == 1:
        return  #will just return None. 
    if number % 2 == 0:
        return find_collatz_nums(number/2)
    return find_collatz_nums((3 * number)   1)

print(find_collatz_nums(3))

why is it in the first code snippet that the return statement will cause an infinite recursion?

I'm just finding myself confused because there's a huge amount of posts here about recursion and answers saying "you need return statements", but I've added them and the code doesn't work.

CodePudding user response：

If you follow your porgram logic this is the sequence of function calls:

find_collatz_nums (3) -> 
find_collatz_nums (10) -> 
find_collatz_nums (5) ->
find_collatz_nums (16) -> 
find_collatz_nums (8) -> 
find_collatz_nums (4) -> 
find_collatz_nums (2) -> 
find_collatz_nums (1) -> find_collatz_nums (1) -> find_collatz_nums (1).... &  so on

So you see there is no way for python to stop this call & it gets called again and again. that's why you need a base condition to return from it.

CodePudding user response：

The first code snippet causes you an infinite loop simply because there is no condition to escape the recursion i.e. print or return anything explicitly.

CodePudding user response：

All your branches are recursive - i.e. they all call the function again. So, you don't actually have a base case. The base case is the one where you actually can compute or return a value directly, instead of recursively computing one.

Consider another problem that you could solve with recursion: finding the sum of numbers in a list:

The base case is when you have the empty list and since there are no values, the sum is just 0.

To think about the recursive case you can slice the list: the first item is a single number and the rest of the list is just another list. The sum for that case is then that first item plus the sum of the rest of the list:

>>> def find_sum(values):
...     if len(values) == 0:
...             return 0
...     else:
...             return values[0]   find_sum(values[1:])
... 
>>> find_sum([1, 2, 3])
6
>>>

I don't know what the Collatz sequence is, so I'll leave it to others to comment on how the recursion should look for that.