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?

In C every execution path of a non-void function has to return a value. — Eugene Sh., Sep 28 '17 at 16:27
Primary rule in programming: just because a program happens to yield correct results every time you've run it so far doesn't mean the program is correct. You kind of lucked out in the first case. A single `int` value is typically returned in the primary accumulator (`ax` in this case if it's x86) and your `return a` that concludes the entire recursion passes a result in `ax` which comes back through every return call, unaltered (since your `gcd` recursive call is the last thing you do). Technically, you should have `return gcd(b, a%b)` for it to be well-defined behavior. — lurker, Sep 28 '17 at 16:40
[Basics of recursion in Python](https://stackoverflow.com/q/30214531/2823755), SO Q&A. — wwii, Sep 28 '17 at 16:55
@EugeneSh. that's incorrect though, they need not return a value, but you must not use the value if one wasn't returned... — Antti Haapala -- Слава Україні, Sep 28 '17 at 17:07
BTW, it's more efficient in Python to do this using a simple `while` loop, rather than using recursion. Unlike some other languages, Python cannot optimize [tail recursion](https://en.wikipedia.org/wiki/Tail_call), so it's best to avoid recursion, unless you're doing something where recursion is appropriate, eg processing recursive data structures, like trees. — PM 2Ring, Sep 28 '17 at 17:10
@AnttiHaapala You are formally correct. Here is the reference http://port70.net/~nsz/c/c11/n1570.html#6.9.1p12 — Eugene Sh., Sep 28 '17 at 17:17
you're missing some understandings in some fundamentals of function calls – [this is an answer I started last night that I'm still working on](https://stackoverflow.com/a/46463482/633183) – it's a big topic and in the context of JavaScript, but many of the issues are relevant to you as python does not offer tail call optimisation — Mulan, Sep 28 '17 at 22:41
take with a grain of salt remarks of *"just use a `while` loop"* or *"recursion isn't efficient"* or *"recursion isn't stack-safe"* – heading these advices will only shortcut you to a misunderstanding over an insanely powerful construct (recursion) – [overcoming a language's shortcomings](https://stackoverflow.com/a/43596323/633183) is a fun and rewarding challenge and can give you a deep understanding of the topic matter – again, these techniques are described in JS, but all of them use pure, functional expressions with a single imperative construct for the loop; all possible in python too — Mulan, Sep 28 '17 at 22:47

Antti Haapala -- Слава Україні · Accepted Answer · 2017-09-28T16:58:31.413

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.

but if the value function gonna 'return' is by 'return a' statement why do we need to provide a return before recursive call? — shashank2806, Sep 28 '17 at 17:01
@SHASHANKSHEKHAR because that gives the return value for only the *innermost* layer of the onion... Incidentally here it is turtles ... `a` all the way down, but the outermost layers need not return *that* one. — Antti Haapala -- Слава Україні, Sep 28 '17 at 17:02

score 2 · Answer 2 · answered Sep 28 '17 at 16:27

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

where to use return in recursion

2 Answers2