Return function in recursion

Question

Understanding the use of return statement in recursion

For example in Binary Search:

def binary_search_recur(array,start,end,item):

    middle = int((start+end)/2)
    #print (middle)
    if (start>end):
        return -1
    else:   
        if array[middle]==item:
            return middle
        elif array[middle]>item:
            return binary_search_recur(array,start,middle-1,item)
        else:
            return binary_search_recur(array,middle+1,end,item)

Calling the function with

array = [27,45,76,81,92,101,291]
binary_search_recur(array,0,len(array)-1,27)

Works fine if I add return statement everywhere, but it does not return 0 (the index of the searched element in the example) if I remove the return statement like below

else:   
      if array[middle]==item:
           return middle
      elif array[middle]>item:
           binary_search_recur(array,start,middle-1,item) #retrun statement removed
      else:
           binary_search_recur(array,middle+1,end,item)   #retrun statement removed

My point is, i would want to return when I find the element so I return the index middle, or if the element is not present at all so in that case I return -1, otherwise I am just calling the function recursively with updated start and end index, Just like merge sort

merge_sort(l)
merge_sort(r)
merge(l,r,array)

So I dont understand why removing the return statement like in the example does not return the op. Any suggestions would be great.

You're calling the function whether you return its result or not. If you don't return the result, that invocation of the function will return `None` when it exits the `if` block. — Nick, Apr 27 '20 at 06:36
Your *first* invocation of the function will recursively call itself but never return the result. So, without return you'd get a call chain `fn` (first time) -> `fn` (second time) but the result of `fn()` (second time) is just ignored. No different to just calling a non-recursive function that doesn't do a `return`. Or more properly having something like `if True: return 1 else: 1;` and expecting a return value for `fn(False)` — VLAZ, Apr 27 '20 at 06:40
Does this answer your question? [Why does my recursive function return None?](https://stackoverflow.com/questions/17778372/why-does-my-recursive-function-return-none) — VLAZ, Apr 27 '20 at 06:41
To be clear: you don't understand why an expression that doesn't start with `return` is not returned? — TigerhawkT3, Apr 27 '20 at 06:57
@TigerhawkT3 Yes, my confusion is I am calling the recursion with updated start and end so there is noting to return unless I find the element or if the element is not present at all. — data_person, Apr 27 '20 at 06:59

score 1 · Answer 1 · answered Apr 27 '20 at 06:39

1

Idea of recurring function is that it returns new execution of itself with new parameters or final value.

You need to return result of next method in recurring loop. If not, Python returns None and result of your inner recurring functions aren't saved anywhere.

answered Apr 27 '20 at 06:39

ex4

2,289
1
14
21

But it works fine for merge sort without the return statement, so I dont understand the difference? – data_person Apr 27 '20 at 06:41
@vikky is merge sorting mutating its input in-place? – VLAZ Apr 27 '20 at 06:42
@vikky Because merge sort modifies the given list inplace and there is no return value. – glglgl Apr 27 '20 at 06:42
@glglgl my understanding is merge sort is not a in-place sorting algorithm since it creates copy of the recursed arrays unlike quick sort. – data_person Apr 27 '20 at 06:46
@VLAZ no it does not mutate in place, it creates copies. So the requirement of return statement falls to modification of in-place array, variable etc. – data_person Apr 27 '20 at 06:47

score 1 · Answer 2 · answered Apr 27 '20 at 06:50

Let's consider the following input

array = [0,1,2,3,4]
item = 1

Your function takes the following steps

start = 0, end = 4, middle = 2.

In this case in your function body, you enter the part with elif array[middle]>item. Then your recursive function calls a second recursive function with the following input

start = 0, end = 1, middle = 0.

In this case you enter the very last else block. Then you call a third function with the following input

start = 1, end = 1, middle = 1.

Now the magic begins. You function finds middle, and returns 1. This takes you back to the line with your 2nd recursive function. Your 2nd recursive function returns 1 and it takes you back to your 1st recursive function, and finally it returns 1 too.

If you delete those returns. In this example, step 1 and 2 return nothing, in other words None.

score 1 · Accepted Answer · answered Apr 27 '20 at 07:22

There's nothing special to recursion - it's just plain functions calls and the fact that the function is calling itself is actually totally irrelevant -, and return works just the same as everywhere else.

Consider this:

def a(arg):
    return arg +1 

def b(arg):
    return a(arg * 2)

def main():
    result = b(42)
    print(result)

If you remove the return in b ie:

def b(arg):
    a(arg * 2)

then technically what you actually wrote is:

def b(arg):
    a(arg * 2)
    return None

since when they end up without an explicit return statement, Python functions implicitely return None. And as a result, in main(), result will be None instead of (arg * 2) + 1

It's the exact same thing happening in your code - if you don't explicitely return the result of the recursive call (=> once again, the fact it's a recursive call is technically totally irrelevant, it works exactly the same way), your function will return None, just has if you wrote:

    elif array[middle]>item:
        binary_search_recur(array,start,middle-1,item)
        return None
    else:
        binary_search_recur(array,middle+1,end,item)
        return None

thanks for the detailed explanation, I understand this now. But if we consider this , I am confused on how does merge sort work without the ```return``` statement. So the presence of return statement is decided upon mutation of the array, variable passed in the function? — data_person, Apr 27 '20 at 07:34
This is still the same as with just any other function - either your function works by returning a new object (in which case you need the return statements obviously) or by mutating it's argument(s) in place - in which case there's no need to return anything, and the convention in this case is indeed to return `None` (cf all the builtin type methods that mutate the current instance in place is `list.sort()` etc). IOW you either return a new value OR (exclusive OR) mutate your argument in place. And once again, just consider the recursive call as a plain ordinary call - that's what it is — bruno desthuilliers, Apr 27 '20 at 08:30

score 0 · Answer 4 · answered Apr 27 '20 at 07:38

0

The point is that you have to "return the returned value".

for example when the following condition passes:

array[middle]>item

your method is not returning anything. so python will return None instead.

answered Apr 27 '20 at 07:38

alireza yazdandoost

634
7
11

Return function in recursion

4 Answers4