Функция возврата в рекурсии

Question

Понимание использования оператора return в recursion

Например, в бинарном поиске:

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)

Вызов функции с помощью

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

Работает хорошо, если я добавлю оператор return везде, но он не вернет 0 (индекс искомого элемента в примере), если я удалю оператор return, как показано ниже

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

Моя точка зрения Я хотел бы вернуться, когда я найду элемент, поэтому я возвращаю индекс middle, или если элемент вообще отсутствует, поэтому в этом случае я возвращаю -1, в противном случае я просто рекурсивно вызываю функцию с обновленным start и end index, так же, как сортировка слиянием

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

Так что я не понимаю, почему удаление оператора return, как в примере, не возвращает op. Любые предложения будут великолепны.

Answer 1

Давайте рассмотрим следующий ввод

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

Ваша функция выполняет следующие шаги

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

В этом случае в теле функции вы вводите деталь с помощью elif array[middle]>item. Затем ваша рекурсивная функция вызывает вторую рекурсивную функцию со следующим вводом

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

В этом случае вы вводите самый последний блок else. Затем вы вызываете третью функцию со следующим вводом

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

Теперь начинаются волхвы c. Ваша функция находит middle и возвращает 1. Это возвращает вас к строке с вашей второй рекурсивной функцией. Ваша вторая рекурсивная функция возвращает 1 и возвращает вас к вашей первой рекурсивной функции, и, наконец, она также возвращает 1.

Если вы удалите эти возвраты. В этом примере шаги 1 и 2 ничего не возвращают, другими словами None.

Answer 2

В рекурсии нет ничего особенного - это просто простые вызовы функций, и тот факт, что функция вызывает сама себя, на самом деле совершенно не имеет значения - и return работает так же, как и везде.

Учтите это:

def a(arg):
    return arg +1 

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

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

Если вы удалите return в b ie:

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

, то технически вы фактически написали:

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

, поскольку, когда они заканчиваются без явного оператора return, функции Python неявно возвращают None. И как результат, main(), result будет None вместо (arg * 2) + 1

Это то же самое 1026 *, происходящее в вашем коде - если вы этого не сделаете явным образом вернуть результат рекурсивного вызова (=> еще раз, тот факт, что это рекурсивный вызов технически совершенно не имеет значения, он работает точно точно так же), ваша функция вернет None, только если Вы писали:

    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

Answer 3

Идея повторяющейся функции заключается в том, что она возвращает новое выполнение самой себя с новыми параметрами или конечным значением.

Вам необходимо вернуть результат следующего метода в повторяющейся l oop. Если нет, Python возвращает None, и результат ваших внутренних повторяющихся функций нигде не сохраняется.

Answer 4

Дело в том, что вы должны "вернуть возвращаемое значение".

, например, когда выполняется следующее условие:

array[middle]>item

ваш метод не возвращать что-нибудь. поэтому python вернет None.