where to use return in recursion

Question

In C this code works, here I did't use return while calling function recursively. It gives correct output

int gcd(int a, int b)
{
    if(b == 0)
        return a;
    gcd(b, a % b);
}

But, If I write same code in python this code returns None (I think value should be returned from the return statement inside if condition)

def gcd(a, b):
    if b == 0:
        return a
    gcd(b, a % b)

To make this code work , I have to add return

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

but why? What is under the hood difference between code execution in C and Python? code in C also works if I add an extra return while calling recursively, Why doesn't it throws an error?

Answer 1

Why? False assumptions. Incidentally this is not a question about Python, but about C.

Your C code is invalid. It has undefined behaviour because you use the returned value of a function call where the control path didn't use the return statement to actually return one. Your compiler probably would have warned about this if you compile with correct options/settings. I.e. This is not how you compile C programs:

% gcc -c 123.c

Instead, you enable all warnings, make them into errors. For example in GCC -Wall, -Wextra, -Werror and -pedantic

% gcc -c 123.c -Wall -Wextra -Werror -pedantic
123.c: In function ‘gcd’:
123.c:6:1: error: control reaches end of non-void function [-Werror=return-type]
 }
 ^
cc1: all warnings being treated as errors

Unfortunately, there are all sorts of bad code around, which means that C compilers are more permissive by default than really necessary. Another problem is that omitting a return statement in C is not even wrong - just using the garbage return value is.

Python doesn't have C-like undefined behaviour, therefore when you omit return statement, the function returns None implicitly, and you don't get some random garbage that makes look as if your broken code worked.

---

A more correct function definition would be

int gcd(int a, int b)
{
    if(b == 0)
        return a;
    return gcd(b, a % b);
}

However perhaps these arguments should be unsigned ints so that you don't get the idea that this would always work correctly for negative numbers.