Основы рекурсии в Python

«Запишите рекурсивную функцию« listSum », которая берет список целых чисел и возвращает сумму всех целых чисел в списке».

Пример:

  • Python: рекурсивная функция для поиска наибольшего числа в списке
  • Перекрестное произведение множеств с использованием рекурсии
  • Регулярное выражение для обнаружения замкнутых циклов C ++ для циклов while и while
  • Рекурсивно найти k-й по величине int в списке списка int в Python
  • Какова максимальная глубина рекурсии в Python и как ее увеличить?
  • Как изменить список с помощью рекурсии в Python?
  • >>>> listSum([1,3,4,5,6]) 19 

    Я знаю, как сделать это по-другому, но не рекурсивным образом.

     def listSum(ls): i = 0 s = 0 while i < len(ls): s = s + ls[i] i = i + 1 print s 

    Мне нужен базовый способ сделать это, поскольку специальные встроенные функции не допускаются.

  • рекурсивная функция python, которая печатает от 0 до n?
  • Рекурсивно построить иерархическое дерево JSON?
  • Ошибка рекурсивной функции Python: «максимальная глубина рекурсии»
  • Перекрестное произведение множеств с использованием рекурсии
  • Почему удаление другого замедляет мой код?
  • Комбинации замков для динамического размера замка
  • 3 Solutions collect form web for “Основы рекурсии в Python”

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

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

    Например,

     listSum([1, 3, 4, 5, 6]) = 1 + listSum([3, 4, 5, 6]) = 1 + (3 + listSum([4, 5, 6])) = 1 + (3 + (4 + listSum([5, 6]))) = 1 + (3 + (4 + (5 + listSum([6])))) = 1 + (3 + (4 + (5 + (6 + listSum([]))))) 

    Теперь, что должно быть результатом listSum([]) ? Это должно быть 0. Это называется базовым условием вашей рекурсии. Когда выполняется базовое условие, рекурсия подходит к концу. Теперь попробуем его реализовать.

    Главное здесь, разбивая список. Вы можете использовать нарезку для этого.

    Простая версия

     >>> def listSum(ls): ... # Base condition ... if not ls: ... return 0 ... ... # First element + result of calling `listsum` with rest of the elements ... return ls[0] + listSum(ls[1:]) >>> >>> listSum([1, 3, 4, 5, 6]) 19 

    Рекурсия хвостового вызова

    Как только вы поймете, как работает вышеупомянутая рекурсия, вы можете попытаться сделать ее немного лучше. Теперь, чтобы найти фактический результат, мы также зависим от значения предыдущей функции. Оператор return не может сразу вернуть значение до тех пор, пока рекурсивный вызов не вернет результат. Мы можем избежать этого, передавая ток параметру функции, как это

     >>> def listSum(ls, result): ... if not ls: ... return result ... return listSum(ls[1:], result + ls[0]) ... >>> listSum([1, 3, 4, 5, 6], 0) 19 

    Здесь мы передаем начальное значение суммы в параметрах, которое равно нулю в listSum([1, 3, 4, 5, 6], 0) . Затем, когда выполняется базовое условие, мы фактически накапливаем сумму в параметре result , поэтому возвращаем его. Теперь последний оператор return имеет listSum(ls[1:], result + ls[0]) , где мы добавляем первый элемент к текущему result и передаем его снова на рекурсивный вызов.

    Это может быть подходящее время для понимания Tail Call . Это не было бы уместно для Python, поскольку он не оптимизировал Tail call.


    Прохождение индексной версии

    Теперь вы можете подумать, что мы создаем так много промежуточных списков. Можно ли это избежать?

    Конечно вы можете. Вам просто нужен индекс элемента для последующей обработки. Но теперь базовое условие будет другим. Поскольку мы собираемся передавать индекс, как мы определяем, как весь список был обработан? Ну, если индекс равен длине списка, мы обработаем все элементы в нем.

     >>> def listSum(ls, index, result): ... # Base condition ... if index == len(ls): ... return result ... ... # Call with next index and add the current element to result ... return listSum(ls, index + 1, result + ls[index]) ... >>> listSum([1, 3, 4, 5, 6], 0, 0) 19 

    Внутренняя функциональная версия

    Если вы посмотрите на определение функции сейчас, вы передаете ему три параметра. Допустим, вы собираетесь выпустить эту функцию как API. Будет ли удобно пользователям передавать три значения, когда они действительно находят сумму списка?

    Неа. Что мы можем с этим поделать? Мы можем создать еще одну функцию, которая является локальной для функции listSum и мы можем передать ей все связанные с реализацией параметры, например

     >>> def listSum(ls): ... ... def recursion(index, result): ... if index == len(ls): ... return result ... return recursion(index + 1, result + ls[index]) ... ... return recursion(0, 0) ... >>> listSum([1, 3, 4, 5, 6]) 19 

    Теперь, когда listSum , он просто возвращает возвращаемое значение внутренней функции recursion , которое принимает index и параметры result . Теперь мы передаем только эти значения, а не пользователи listSum . Им просто нужно передать список для обработки.

    В этом случае, если вы наблюдаете параметры, мы не передаем ls в recursion но мы используем ее внутри. ls доступен внутри recursion из-за свойства закрытия.


    Версия параметров по умолчанию

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

     >>> def listSum(ls, index=0, result=0): ... # Base condition ... if index == len(ls): ... return result ... ... # Call with next index and add the current element to result ... return listSum(ls, index + 1, result + ls[index]) ... >>> listSum([1, 3, 4, 5, 6]) 19 

    Теперь, если вызывающий объект явно не передает какое-либо значение, тогда 0 будет присвоен как index и result .


    Рекурсивная проблема питания

    Теперь давайте применим идеи к другой проблеме. Например, попробуйте реализовать функцию power(base, exponent) . Он вернет значение base поднятой до exponent мощности.

     power(2, 5) = 32 power(5, 2) = 25 power(3, 4) = 81 

    Теперь, как мы можем сделать это рекурсивно? Попытаемся понять, как эти результаты достигнуты.

     power(2, 5) = 2 * 2 * 2 * 2 * 2 = 32 power(5, 2) = 5 * 5 = 25 power(3, 4) = 3 * 3 * 3 * 3 = 81 

    Хммм, так мы поняли. base умножается на себя, время exponent дает результат. Хорошо, как мы к этому подходим. Попробуем определить решение с той же функцией.

     power(2, 5) = 2 * power(2, 4) = 2 * (2 * power(2, 3)) = 2 * (2 * (2 * power(2, 2))) = 2 * (2 * (2 * (2 * power(2, 1)))) 

    Каким должен быть результат, если что-то поднято до власти 1? Результат будет такого же числа, не так ли? Мы получили базовое условие для нашей рекурсии 🙂

      = 2 * (2 * (2 * (2 * 2))) = 2 * (2 * (2 * 4)) = 2 * (2 * 8) = 2 * 16 = 32 

    Хорошо, давайте его реализовать.

     >>> def power(base, exponent): ... # Base condition, if `exponent` is lesser than or equal to 1, return `base` ... if exponent <= 1: ... return base ... ... return base * power(base, exponent - 1) ... >>> power(2, 5) 32 >>> power(5, 2) 25 >>> power(3, 4) 81 

    Хорошо, как будет определяться оптимизированная версия Tail call? Позволяет передать текущий результат в качестве параметра самой функции и вернуть результат при выполнении базового условия. Давайте сделаем это простым и применим подход по умолчанию по умолчанию.

     >>> def power(base, exponent, result=1): ... # Since we start with `1`, base condition would be exponent reaching 0 ... if exponent <= 0: ... return result ... ... return power(base, exponent - 1, result * base) ... >>> power(2, 5) 32 >>> power(5, 2) 25 >>> power(3, 4) 81 

    Теперь мы уменьшаем значение exponent в каждом рекурсивном вызове и множественный result с base и передаем его рекурсивному вызову power . Начнем со значения 1 , потому что мы обратимся к проблеме в обратном порядке. Рекурсия будет происходить так

     power(2, 5, 1) = power(2, 4, 1 * 2) = power(2, 4, 2) = power(2, 3, 2 * 2) = power(2, 3, 4) = power(2, 2, 4 * 2) = power(2, 2, 8) = power(2, 1, 8 * 2) = power(2, 1, 16) = power(2, 0, 16 * 2) = power(2, 0, 32) 

    Поскольку exponent становится равным нулю, базовое условие выполняется и result будет возвращен, поэтому мы получаем 32 🙂

    Ранний выход типичен для рекурсивных функций. seq является ложным, когда пуст (поэтому, когда нет цифр, оставшихся для суммирования).

    Синтаксис Slice позволяет передавать последовательность в рекурсивно называемую функцию без целого, потребляемого на текущем этапе.

     def listSum(seq): if not seq: return 0 return seq[0] + listSum(seq[1:]) print listSum([1,3,4,5,6]) # prints 19 
     def listSum(L): """Returns a sum of integers for a list containing integers. input: list of integers output: listSum returns a sum of all the integers in L. """ if L == []: return [] if len(L) == 1: return L[0] else: return L[0] + listSum(L[1:]) print listSum([1, 3, 4, 5, 6]) print listSum([]) print listSum([8]) 
    Python - лучший язык программирования в мире.