where to use return in recursion

user_7511615 0
Viewed 277

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?

greatest-common-divisor recursion c python
2 Answers

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.

user_9189590

The code in C has undefined behavior, there is no return statement on the second code path (recursive call). You're lucky that return value is always kept in the same register and not overwritten, but it is not guaranteed and you may get junk.

Python explicitly treats missing return paths as return None

user_27090180
Related