Рекурсивная функция, возвращающая ни одного?

Question

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

def bisect(input, target): 
    mid = len(input)/ 2 
    if len(input) == 1: 
     if input[0] == target: 
      return 1 
     else: 
      return None 
    elif input[mid] > target: 
     bisect(input[:mid], target) 
    elif input[mid] <= target: 
     bisect(input[mid:], target) 

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

Когда я называю bisect(['d','e'], 'd') моя функция должна возвращать значение

bisect(['d'], 'd') 

, но вместо этого он возвращает None. Кроме того, когда я вызываю bisect(['d'], 'd') напрямую, я получаю правильное значение 0. Как это возможно?

Answer 1

Вы игнорируете возвращаемые значения рекурсивных вызовов. Вам нужно явно вернуть их тоже:

elif input[mid] > target: 
    return bisect(input[:mid], target) 
elif input[mid] <= target: 
    return bisect(input[mid:], target) 

рекурсивные вызовы так же, как и любой другой вызов функции; они возвращают результат вызывающему. Если вы проигнорируете возвращаемое значение, а функция вызова закончится, вы получите эту функцию вызова, а затем верните None.