Recursive Functions in Python vs C

Question

It seems as if C allows for a function to reference itself (in a recursive manner) when executing, for example, the Collatz conjecture.

int collatz(int n);

int main(void)
{
    int result = collatz(9);
    printf("Steps: %i\n", result);
}

int collatz(int n)
{
    if (n == 1)
        return 0;
    else if ((n % 2) == 0)
        return 1 + collatz(n / 2);
    else
        return 1 + collatz(3 * n + 1);
}

Python gives me an error when I try this:

TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'

when I reference the same function within itself:

def collatz_recursive(n):

    while n != 1:
        if n % 2 == 0:
            return 1 + collatz_recursive(n/2)
        else:
            return 1 + collatz_recursive(n * 3 + 1)

However, when I place collatz in its own function and reference it from the outside with collatz_recursive I don't have that problem:

def collatz(n):
    while n != 1:
        if n % 2 == 0:
            n = n/2
        else:
            n = n * 3 + 1

def collatz_recursive(n):
    while n != 1:
        if n % 2 == 0:
            return 1 + collatz(n/2)
        else:
            return 1 + collatz(n * 3 + 1)

There's no loop in your C examples, why do you add it in python? — Olvin Roght
– Olvin Roght, Commented Nov 24, 2020 at 20:55
Python allows recursive functions, you're not telling the whole story. Or, maybe, you failed to reduce the story to a minimal reproducible example first. — Ulrich Eckhardt
– Ulrich Eckhardt, Commented Nov 24, 2020 at 20:55
Did you notice that your C code doesn't use while at all? Your Python code fails not because of any Python language limitation, but because you messed up porting your code. — user2357112
– user2357112, Commented Nov 24, 2020 at 20:56
Your first Python function is lacking the if n == 1 part of the C function — UnholySheep
– UnholySheep, Commented Nov 24, 2020 at 20:56

amirhe · Accepted Answer · 2020-11-24 21:06:17Z

3

The 'int' and 'NoneType' can not be added through + operation.

Here is my console for running your very last code:

 line 13, in collatz_recursive
    return 1 + collatz(n * 3 + 1)
TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'

I think the problem is that you forgot to handle the edge-case n=1 for your collatz_recursive function, you can easily log n by putting a print function before and after while loop and observe the bug.

Try to return a default value for your function, this is also named base-case. You can read more about recursion and base case in here

answered Nov 24, 2020 at 21:06

amirhe

2,3511 gold badge18 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Olvin Roght · Accepted Answer · 2020-11-24 21:08:56Z

2

"Python gives me an error when ... I reference the same function within itself"

No, Python gives you an error because collatz_recursive doesn't return a value for n == 1. The return value of a function is None if no value was returned with a return statement.

Your Python code should look like

def collatz_recursive(n):

    if n == 1:
        return 0
    if n % 2 == 0:
        return 1 + collatz_recursive(n/2)
    else:
        return 1 + collatz_recursive(n * 3 + 1)

edited Nov 24, 2020 at 21:08

Olvin Roght

7,8432 gold badges19 silver badges39 bronze badges

answered Nov 24, 2020 at 21:02

Thomas Sablik

16.5k7 gold badges38 silver badges69 bronze badges

Collectives™ on Stack Overflow

Recursive Functions in Python vs C

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related