Главная страница » Что такое рекурсия в питоне

Что такое рекурсия в питоне

  • автор:

10. Рекурсия и исключения¶

До сих пор мы встречались с двумя составными типами: строки, состоящие из символов, и списки, состоящие из элементов любого типа. Одно из отмеченных нами различий между этими типами состоит в том, что элементы списка можно изменять, а символы строки — нельзя. Другими словами, строки являются неизменяемыми, а списки — изменяемыми.

Кортеж (англ.: tuple), как и список, представляет собой последовательность элементов любого типа. Но, в отличие от списков, кортежи неизменяемы. Синтаксически, кортеж — это последовательность разделенных запятыми значений:

Хотя это не является обязательным, принято заключать кортежи в скобки:

Для того, чтобы создать кортеж с единственным элементом, нужно поставить запятую после единственного элемента:

Без запятой Python считает, что (5) — это целое число в скобках:

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

Оператор срез выбирает диапазон элементов.

Однако, если попробовать выполнить присваивание элементу кортежа, то получим ошибку:

И, разумеется, хотя мы и не можем изменить отдельный элемент кортежа, мы можем заменить кортеж на другой кортеж:

Или, вместо этого, мы могли бы сначала преобразовать кортеж в список, изменить список, и затем преобразовать его обратно в кортеж:

10.2. Присваивание кортежей¶

Время от времени возникает необходимость обменять значения двух переменных. Пользуясь традиционными предложениями присваивания, мы должны использовать временную переменную. Например, чтобы обменять значения переменных a и b :

Если нам придется делать это часто, такой подход покажется громоздким. Python предоставляет возможность присваивания кортежей, которая элегантно решает эту задачу:

В левой части у нас кортеж из двух переменных; в правой — кортеж из двух значений. Каждое значение присваивается соответствующей ему переменной. Все выражения в правой части вычисляются до того, как выполняется первое присваивание. Это свойство делает присваивание кортежа очень полезным инструментом.

Само собой разумеется, что количество переменных в левой части и количество значений в правой должны быть одинаковы:

10.3. Кортежи как возвращаемые значения¶

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

После чего мы сможем присвоить возвращаемое значение кортежу из двух переменных:

В данном случае мы не получаем никаких преимуществ, реализовав обмен значений с помощью функции swap . Кроме того, пытаясь реализовать обмен значений как функцию swap , есть опасность совершить ошибку:

Если вызвать эту функцию так:

то a и x будут альтернативными именами для одного и того же значения. Изменение x в функции swap приводит к тому, что x указывает на другое значение, но это никак не отразится на переменной a в __main__ . Аналогично, изменение y никак не повлияет на b .

Функция выполняется без сообщений об ошибке, но она не делает того, что от нее ожидается. Это пример семантической ошибки.

10.4. Еще раз о чистых и модифицирующих функциях¶

Ранее в разделе Чистые и модифицирующие функции мы обсуждали чистые функции и модифицирующие функции в связи со списками. Поскольку кортежи неизменяемы, нельзя написать функцию, модифицирующую кортеж.

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

Убедимся, что она работает:

Но если мы попробуем вызвать ее с кортежем, то получим ошибку:

Проблема в том, что кортежи неизменяемы, и не поддерживают присваивание срезу. Простое решение заключается в том, чтобы сделать insert_in_middle чистой функцией:

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

Теперь можно написать версию insert_in_middle , работающую с последовательностями всех встроенных типов:

Две последние версии insert_in_middle являются чистыми функциями. У них нет побочных эффектов. Добавив encapsulate и последнюю версию insert_in_middle в модуль seqtools.py , мы сможем протестировать функцию:

Значения my_string , my_list и my_tuple не изменились. Если мы захотим использовать insert_in_middle для их изменения, нам придется присваивать возвращаемое функцией значение обратно переменной:

10.5. Рекурсивные структуры данных¶

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

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

Вложенный список чисел — это список, элементы которого относятся к одному из двух типов:

  1. числа
  2. вложенные списки чисел

Заметьте, что термин ‘вложенный список чисел’ использован в его собственном определении. Рекурсивные определения, подобные этому, довольно распространены в математике и программировании. Они предоставляют краткий и мощный способ описать рекурсивные структуры данных, частично состоящие из меньших и более простых экземпляров самих себя. Структура не циклична, поскольку рано или поздно мы достигаем списка, который не содержит других списков в качестве элементов.

Теперь предположим, что наша задача — написать функцию, которая просуммирует голоса во вложенном списке чисел. В Python имеется встроенная функция, которая вычисляет сумму последовательности чисел:

Для нашего вложенного списка чисел, однако, функция sum не работает:

Проблема в том, что третий элемент этого списка, [11, 13] , сам является списком, а список не может быть просуммирован с целыми числами 1 , 2 и 8 .

10.6. Рекурсия¶

Для того, чтобы просуммировать все числа в нашем вложенном списке чисел, нам нужно обойти список, обработав каждый элемент его многоуровневой структуры. Числовые элементы будем складывать, а для списочных элементов повторять этот же обход.

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

Тело функции recursive_sum содержит цикл for , который реализует обход nested_num_list . Если element оказывается числом (ветка else ), он прибавляется к sum . Если element — список, то вновь вызывается recursive_sum с этим элементом в качестве аргумента. Предложение внутри определения функции, которое вызывает эту же функцию, называют рекурсивным вызовом функции.

Рекурсия поистине один из самых красивых и элегантных инструментов в программировании.

Несколько более сложной задачей является нахождение самого большого числа в нашем вложенном списке чисел:

Приведенные доктесты демонстрируют recursive_max в работе.

Дополнительная хитрость потребовалась для нахождения числового значения для инициализации переменной largest . Мы не можем просто использовать nested_num_list[0] , так как это может быть либо число, либо список. Для решения этой задачи мы воспользовались циклом while, в котором присваиваем largest первое из найденных числовых значений, и неважно, насколько глубоко оно вложено.

Два приведенных примера оба имеют базовый случай который не приводит к рекурсивному вызову: случай, когда элемент является числом, а не списком. Без базового случая мы получили бы бесконечную рекурсию, и программа бы не работала. Python бы прекратил выполнение программы, достигнув максимально разрешенной глубины рекурсии, и возвратил ошибку выполнения.

Создайте файл infinite_recursion.py со следующим кодом:

Перейдя в каталог, где вы сохранили файл, введите в командной строке:

После того, как промелькнут и остановятся сообщения, вы увидите конец длинной последовательности сообщений об ошибках — распечатки стека вызовов:

Мы, конечно же, не хотим, чтобы что-то подобное получил пользователь, запустив одну из наших программ. Поэтому, прежде чем завершить обсуждение рекурсии, давайте посмотрим, как в Python обрабатываются ошибки, подобные этой.

10.7. Исключения¶

Каждый раз, когда происходит ошибка выполнения, создается исключение (англ.: exception). Программа прекращает выполняться и Python распечатывает стек вызовов, где в конце идет сообщение о возникшем исключении.

Например, деление на ноль создает исключение:

Так же, как и попытка прочитать несуществующий элемент списка:

Или попытка присвоить значение элементу кортежа:

Во всех случаях сообщение об ошибке на последней строке состоит из двух частей: тип ошибки перед двоеточием, и конкретное описание ошибки после него.

Иногда необходимо выполнить операцию, которая может вызвать исключение, но мы не хотим, чтобы программа останавливалась. В этом случае можно организовать обработку исключений, используя предложения try и except .

Например, мы можем попросить пользователя ввести имя файла, и затем попробовать открыть его. Но мы не хотим, чтобы программа сломалась, если файл не существует; мы хотим обработать вероятное исключение:

Предложение try выполняет предложения в первом блоке. Если исключения не происходит, предложение except игнорируется. Если же возникает исключение, то выполняются предложения блока except , после чего выполнение программы продолжается.

Можно встроить эту конструкцию в функцию exists (англ.: существует), которая принимает в качестве параметра имя файла и возвращает True , если файл существует, и False , если он не существует:

Можно использовать несколько блоков except для того, чтобы обрабатывать различные исключения (см. урок Errors and Exceptions в учебнике Python Tutorial от создателя Python Гвидо ван Россума).

Если ваша программа обнаруживает ошибочную ситуацию, то она может возбудить (англ.: raise) исключение. Вот пример, в котором принимается ввод от пользователя и проверяется, что введенное число неотрицательно.

Предложение raise принимает два аргумента: тип исключения, и конкретное описание ошибки. ValueError является встроенным типом исключения, который лучше всего подходит в данной ситуации. Полный список встроенных исключений можно найти в разделе 2.3 Справочника по библиотеке Python, также написанного создателем Python Гвидо ван Россумом.

Если функция, вызывающая get_age , обрабатывает ошибку, то программа может продолжить выполняться. Иначе Python распечатывает стек вызовов и завершается:

Сообщение об ошибке включает тип ошибки и дополнительную информацию, которую вы указали.

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

Запустите эту версию и посмотрите на результат.

10.8. Хвостовая рекурсия¶

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

Вот версия функции countdown из главы 6, написанная с использованием хвостовой рекурсии:

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

Рекурсивно определяются некоторые из хорошо известных математических функций. Например, факториал, для которого имеется собственный оператор, ! , определяется так:

Можно легко закодировать это на Python:

Другой пример, хорошо известный из математики — это последовательность Фибоначчи, определяемая так:

Это тоже можно с легкостью записать на языке Python:

Обе функции, и factorial и fibonacci , демонстрируют хвостовую рекурсию.

Однако, хвостовая рекурсия считается плохой практикой в таких языках, как Python, так как она требует больше системных ресурсов, чем эквивалентное решение, использующее итерацию.

Вызов factorial(1000) превысит максимально допустимую глубину рекурсии. Также попробуйте выполнить fibonacci(35) и посмотрите, сколько времени на это понадобится (будьте терпеливы, вы получите результат).

Вам будет предложено написать итеративную версию функции factorial в качестве упражнения. А в следующей главе вы увидите более эффективный способ реализации fibonacci .

10.9. Списочное включение¶

Списочное включение (англ.: list comprehension) — это синтаксическая конструкция, которая позволяет создавать списки из других списков, используя компактную математическую нотацию:

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

Выражение списочного включения имеет тот же эффект, что и следующий код:

Как видите, код, использующий списковое включение, гораздо компактнее.

10.10. Маленький учебный пример: дерево¶

Следующий пример частично реализует поведение программы tree, имеющейся в операционных системах Unix.

Ниже вам будет предложено самостоятельно исследовать эту программу в качестве упражнений.

10.11. Глоссарий¶

10.12. Упражнения¶

Выполните эту программу и объясните результаты:

Объясните, почему эта версия swap не работает, как задумано. Какими будут значения a и b после вызова swap ?

Создайте модуль с именем seqtools.py . Поместите в него функции encapsulate и insert_in_middle из этой главы. Добавьте доктесты, проверяющие, что эти функции работают правильно со всеми тремя встроенными типами последовательностей.

Добавьте следующие функции в seqtools.py :

Как и прежде, напишите тела функций, проверяя их работу с помощью доктестов по готовности каждой новой функции.

Напишите функцию recursive_min , которая возвращает наименьшее число из вложенного списка чисел:

Ваша функция должна успешно пройти доктесты.

Напишите функцию recursive_count , которая возвращает количество вхождений target в nested_number_list :

Ваша функция должна успешно пройти доктесты.

Напишите функцию flatten , которая возвращает (невложенный) список чисел, содержащий все числа из nested_number_list :

Убедитесь, что ваша функция успешно проходит доктесты.

Напишите функцию readposint , которая просит пользователя ввести положительное целое число, и затем проверяет то, что ввел пользователь. Вот как можно работать с такой функцией:

Используйте обработку исключений при проверке введенного пользователем значения.

Предскажите, что выдаст Python в ответ на следующее:

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

Воспользовавшись pydoc или онлайновой документацией на сайте http://docs.python.org/, выясните, что делают функции sys.getrecursionlimit() и sys.setrecursionlimit(n) . Проведите несколько экспериментов, подобных тому, который мы поставили с помощью infinite_recursion.py , чтобы убедиться в том, как работают эти функции.

Перепишите функцию factorial , используя итерацию вместо рекурсии. Вызовите вашу новую функцию с аргументом 1000 и заметьте, как быстро она отработает.

Что такое рекурсия в питоне

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

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

Но если вы напишите функцию,которая будет вызывать саму себя бесконечное количество раз, получите ошибку Recursionerror: maximum recursion depth exceeded. Попробуйте запустить у себя на компьютере следующую программу.

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

Условие выхода называют также базовым случаем — самым простым решением какой-нибудь задачи.

Нахождение факториала с помощью рекурсии

Например, базовым случаем (самым простым случаем) нахождения факториала, является 1! или 0!. Это значение гораздо легче найти, чем например 7! (факториал 7).

Но рекурсии кроме базового случая должен присутствовать рекурсивный случай или шаг рекурсии — это способ сведения задачи к более простой. Например, 5! = 1*2*3*4*5 = 4!*5. То есть, чтобы найти факториал пяти, достаточно знать факториал четырех и умножить это на 5. Тогда в общем виде рекурентная формула нахождения факториала будет выглядеть следующим образом:

А код реализации будет следующим:

Нахождение чисел Фибоначчи

Числа Фибоначчи представляют собой рекурентный ряд чисел — это значит, что в этом ряду должны быть обязательно первые члены ряда (обычно это 0 и 1), а все остальные числа находятся от предыдущих путем сложения двух чисел стоящих перед текущим.

В итоге получаем такой ряд: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 и т.д.

У каждого числа в этом ряду есть свой порядковый номер, начинается нумерация с единицы. И давайте обозначим за F(n) — n-ое число Фибоначчи. И тогда,чтобы найти пятое число Фибоначчи нужно сложить два предыдущих к нему F(5) = F(4)+F(4). А общая формула нахождения будет выглядеть следующим образом:

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

Проверить строку на палиндром(рекурсия)

Палиндром — слово или фраза, которые одинаково читаются слева направо и справа налево.

Строка, состоящая из одного символа, по умолчанию является палиндромом. Это наш базовый или самый простой случай. Также за палиндром мы будет принимать и пустую строку.

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

Ниже представлена рекурсивная функция, которая реализует проверку на палиндром.

Recursion in Python: An Introduction

If you’re familiar with functions in Python, then you know that it’s quite common for one function to call another. In Python, it’s also possible for a function to call itself! A function that calls itself is said to be recursive, and the technique of employing a recursive function is called recursion.

It may seem peculiar for a function to call itself, but many types of programming problems are best expressed recursively. When you bump up against such a problem, recursion is an indispensable tool for you to have in your toolkit.

By the end of this tutorial, you’ll understand:

  • What it means for a function to call itself recursively
  • How the design of Python functions supports recursion
  • What factors to consider when choosing whether or not to solve a problem recursively
  • How to implement a recursive function in Python

Then you’ll study several Python programming problems that use recursion and contrast the recursive solution with a comparable non-recursive one.

Free Bonus: Get a sample chapter from Python Basics: A Practical Introduction to Python 3 to see how you can go from beginner to intermediate in Python with a complete curriculum, up to date for Python 3.9.

What Is Recursion?

The word recursion comes from the Latin word recurrere, meaning to run or hasten back, return, revert, or recur. Here are some online definitions of recursion:

    The act or process of returning or running back The act of defining an object (usually a function) in terms of that object itself A method of defining a sequence of objects, such as an expression, function, or set, where some number of initial objects are given and each successive object is defined in terms of the preceding objects

A recursive definition is one in which the defined term appears in the definition itself. Self-referential situations often crop up in real life, even if they aren’t immediately recognizable as such. For example, suppose you wanted to describe the set of people that make up your ancestors. You could describe them this way:

Recursive definition of ancestors

Notice how the concept that is being defined, ancestors, shows up in its own definition. This is a recursive definition.

In programming, recursion has a very precise meaning. It refers to a coding technique in which a function calls itself.

Why Use Recursion?

Most programming problems are solvable without recursion. So, strictly speaking, recursion usually isn’t necessary.

However, some situations particularly lend themselves to a self-referential definition—for example, the definition of ancestors shown above. If you were devising an algorithm to handle such a case programmatically, a recursive solution would likely be cleaner and more concise.

Traversal of tree-like data structures is another good example. Because these are nested structures, they readily fit a recursive definition. A non-recursive algorithm to walk through a nested structure is likely to be somewhat clunky, while a recursive solution will be relatively elegant. An example of this appears later in this tutorial.

On the other hand, recursion isn’t for every situation. Here are some other factors to consider:

  • For some problems, a recursive solution, though possible, will be awkward rather than elegant.
  • Recursive implementations often consume more memory than non-recursive ones.
  • In some cases, using recursion may result in slower execution time.

Typically, the readability of the code will be the biggest determining factor. But it depends on the circumstances. The examples presented below should help you get a feel for when you should choose recursion.

Recursion in Python

When you call a function in Python, the interpreter creates a new local namespace so that names defined within that function don’t collide with identical names defined elsewhere. One function can call another, and even if they both define objects with the same name, it all works out fine because those objects exist in separate namespaces.

The same holds true if multiple instances of the same function are running concurrently. For example, consider the following definition:

When function() executes the first time, Python creates a namespace and assigns x the value 10 in that namespace. Then function() calls itself recursively. The second time function() runs, the interpreter creates a second namespace and assigns 10 to x there as well. These two instances of the name x are distinct from each another and can coexist without clashing because they are in separate namespaces.

Unfortunately, running function() as it stands produces a result that is less than inspiring, as the following traceback shows:

As written, function() would in theory go on forever, calling itself over and over without any of the calls ever returning. In practice, of course, nothing is truly forever. Your computer only has so much memory, and it would run out eventually.

Python doesn’t allow that to happen. The interpreter limits the maximum number of times a function can call itself recursively, and when it reaches that limit, it raises a RecursionError exception, as you see above.

Technical note: You can find out what Python’s recursion limit is with a function from the sys module called getrecursionlimit() :

You can change it, too, with setrecursionlimit() :

You can set it to be pretty large, but you can’t make it infinite.

There isn’t much use for a function to indiscriminately call itself recursively without end. It’s reminiscent of the instructions that you sometimes find on shampoo bottles: “Lather, rinse, repeat.” If you were to follow these instructions literally, you’d shampoo your hair forever!

This logical flaw has evidently occurred to some shampoo manufacturers, because some shampoo bottles instead say “Lather, rinse, repeat as necessary.” That provides a termination condition to the instructions. Presumably, you’ll eventually feel your hair is sufficiently clean to consider additional repetitions unnecessary. Shampooing can then stop.

Similarly, a function that calls itself recursively must have a plan to eventually stop. Recursive functions typically follow this pattern:

  • There are one or more base cases that are directly solvable without the need for further recursion.
  • Each recursive call moves the solution progressively closer to a base case.

You’re now ready to see how this works with some examples.

Get Started: Count Down to Zero

The first example is a function called countdown() , which takes a positive number as an argument and prints the numbers from the specified argument down to zero:

Notice how countdown() fits the paradigm for a recursive algorithm described above:

  • The base case occurs when n is zero, at which point recursion stops.
  • In the recursive call, the argument is one less than the current value of n , so each recursion moves closer to the base case.

Note: For simplicity, countdown() doesn’t check its argument for validity. If n is either a non-integer or negative, you’ll get a RecursionError exception because the base case is never reached.

The version of countdown() shown above clearly highlights the base case and the recursive call, but there’s a more concise way to express it:

Here’s one possible non-recursive implementation for comparison:

This is a case where the non-recursive solution is at least as clear and intuitive as the recursive one, and probably more so.

Calculate Factorial

The next example involves the mathematical concept of factorial. The factorial of a positive integer n, denoted as n!, is defined as follows:

Definition of factorial

In other words, n! is the product of all integers from 1 to n, inclusive.

Factorial so lends itself to recursive definition that programming texts nearly always include it as one of the first examples. You can express the definition of n! recursively like this:

Recursive definition of factorial

As with the example shown above, there are base cases that are solvable without recursion. The more complicated cases are reductive, meaning that they reduce to one of the base cases:

  • The base cases (n = 0 or n = 1) are solvable without recursion.
  • For values of n greater than 1, n! is defined in terms of (n — 1)!, so the recursive solution progressively approaches the base case.

For example, recursive computation of 4! looks like this:

Factorial illustration

Recursive Calculation of 4!

The calculations of 4!, 3!, and 2! suspend until the algorithm reaches the base case where n = 1. At that point, 1! is computable without further recursion, and the deferred calculations run to completion.

Define a Python Factorial Function

Here’s a recursive Python function to calculate factorial. Note how concise it is and how well it mirrors the definition shown above:

A little embellishment of this function with some print() statements gives a clearer idea of the call and return sequence:

Notice how all the recursive calls stack up. The function gets called with n = 4 , 3 , 2 , and 1 in succession before any of the calls return. Finally, when n is 1 , the problem can be solved without any more recursion. Then each of the stacked-up recursive calls unwinds back out, returning 1 , 2 , 6 , and finally 24 from the outermost call.

Recursion isn’t necessary here. You could implement factorial() iteratively using a for loop:

You can also implement factorial using Python’s reduce() , which you can import from the functools module:

Again, this shows that if a problem is solvable with recursion, there will also likely be several viable non-recursive solutions as well. You’ll typically choose based on which one results in the most readable and intuitive code.

Another factor to take into consideration is execution speed. There can be significant performance differences between recursive and non-recursive solutions. In the next section, you’ll explore these differences a little further.

Speed Comparison of Factorial Implementations

To evaluate execution time, you can use a function called timeit() from a module that is also called timeit . This function supports a number of different formats, but you’ll use the following format in this tutorial:

timeit() first executes the commands contained in the specified <setup_string> . Then it executes <command> the given number of <iterations> and reports the cumulative execution time in seconds:

Here, the setup parameter assigns string the value ‘foobar’ . Then timeit() prints string one hundred times. The total execution time is just over 3/100 of a second.

The examples shown below use timeit() to compare the recursive, iterative, and reduce() implementations of factorial from above. In each case, setup_string contains a setup string that defines the relevant factorial() function. timeit() then executes factorial(4) a total of ten million times and reports the aggregate execution.

First, here’s the recursive version:

Next up is the iterative implementation:

Last, here’s the version that uses reduce() :

In this case, the iterative implementation is the fastest, although the recursive solution isn’t far behind. The method using reduce() is the slowest. Your mileage will probably vary if you try these examples on your own machine. You certainly won’t get the same times, and you may not even get the same ranking.

Does it matter? There’s a difference of almost four seconds in execution time between the iterative implementation and the one that uses reduce() , but it took ten million calls to see it.

If you’ll be calling a function many times, you might need to take execution speed into account when choosing an implementation. On the other hand, if the function will run relatively infrequently, then the difference in execution times will probably be negligible. In that case, you’d be better off choosing the implementation that seems to express the solution to the problem most clearly.

For factorial, the timings recorded above suggest a recursive implementation is a reasonable choice.

Frankly, if you’re coding in Python, you don’t need to implement a factorial function at all. It’s already available in the standard math module:

Perhaps it might interest you to know how this performs in the timing test:

Wow! math.factorial() performs better than the best of the other three implementations shown above by roughly a factor of 10.

Technical note: The fact that math.factorial() is so much speedier probably has nothing to do with whether it’s implemented recursively. More likely it’s because the function is implemented in C rather than Python. For more reading on Python and C, see these resources:

A function implemented in C will virtually always be faster than a corresponding function implemented in pure Python.

Traverse a Nested List

The next example involves visiting each item in a nested list structure. Consider the following Python list:

As the following diagram shows, names contains two sublists. The first of these sublists itself contains another sublist:

Nested list example

Suppose you wanted to count the number of leaf elements in this list—the lowest-level str objects—as though you’d flattened out the list. The leaf elements are «Adam» , «Bob» , «Chet» , «Cat» , «Barb» , «Bert» , «Alex» , «Bea» , «Bill» , and «Ann» , so the answer should be 10 .

Just calling len() on the list doesn’t give the correct answer:

len() counts the objects at the top level of names , which are the three leaf elements «Adam» , «Alex» , and «Ann» and two sublists [«Bob», [«Chet», «Cat»], «Barb», «Bert»] and [«Bea», «Bill»] :

What you need here is a function that traverses the entire list structure, sublists included. The algorithm goes something like this:

  1. Walk through the list, examining each item in turn.
  2. If you find a leaf element, then add it to the accumulated count.
  3. If you encounter a sublist, then do the following:
    • Drop down into that sublist and similarly walk through it.
    • Once you’ve exhausted the sublist, go back up, add the elements from the sublist to the accumulated count, and resume the walk through the parent list where you left off.

Note the self-referential nature of this description: Walk through the list. If you encounter a sublist, then similarly walk through that list. This situation begs for recursion!

Traverse a Nested List Recursively

Recursion fits this problem very nicely. To solve it, you need to be able to determine whether a given list item is leaf item or not. For that, you can use the built-in Python function isinstance() .

In the case of the names list, if an item is an instance of type list , then it’s a sublist. Otherwise, it’s a leaf item:

Now you have the tools in place to implement a function that counts leaf elements in a list, accounting for sublists recursively:

If you run count_leaf_items() on several lists, including the names list defined above, you get this:

As with the factorial example, adding some print() statements helps to demonstrate the sequence of recursive calls and return values:

Here’s a synopsis of what’s happening in the example above:

  • Line 9: isinstance(item, list) is True , so count_leaf_items() has found a sublist.
  • Line 11: The function calls itself recursively to count the items in the sublist, then adds the result to the accumulating total.
  • Line 12: isinstance(item, list) is False , so count_leaf_items() has encountered a leaf item.
  • Line 14: The function increments the accumulating total by one to account for the leaf item.

Note: To keep things simple, this implementation assumes the list passed to count_leaf_items() contains only leaf items or sublists, not any other type of composite object like a dictionary or tuple.

The output from count_leaf_items() when it’s executed on the names list now looks like this:

Each time a call to count_leaf_items() terminates, it returns the count of leaf elements it tallied in the list passed to it. The top-level call returns 10 , as it should.

Traverse a Nested List Non-Recursively

Like the other examples shown so far, this list traversal doesn’t require recursion. You can also accomplish it iteratively. Here’s one possibility:

If you run this non-recursive version of count_leaf_items() on the same lists as shown previously, you get the same results:

The strategy employed here uses a stack to handle the nested sublists. When this version of count_leaf_items() encounters a sublist, it pushes the list that is currently in progress and the current index in that list onto a stack. Once it has counted the sublist, the function pops the parent list and index from the stack so it can resume counting where it left off.

In fact, essentially the same thing happens in the recursive implementation as well. When you call a function recursively, Python saves the state of the executing instance on a stack so the recursive call can run. When the recursive call finishes, the state is popped from the stack so that the interrupted instance can resume. It’s the same concept, but with the recursive solution, Python is doing the state-saving work for you.

Notice how concise and readable the recursive code is when compared to the non-recursive version:

Comparison of non-recursive and recursive list traversal algorithms

Recursive vs Non-Recursive Nested List Traversal

This is a case where using recursion is definitely an advantage.

Detect Palindromes

The choice of whether to use recursion to solve a problem depends in large part on the nature of the problem. Factorial, for example, naturally translates to a recursive implementation, but the iterative solution is quite straightforward as well. In that case, it’s arguably a toss-up.

The list traversal problem is a different story. In that case, the recursive solution is very elegant, while the non-recursive one is cumbersome at best.

For the next problem, using recursion is arguably silly.

A palindrome is a word that reads the same backward as it does forward. Examples include the following words:

  • Racecar
  • Level
  • Kayak
  • Reviver
  • Civic

If asked to devise an algorithm to determine whether a string is palindromic, you would probably come up with something like “Reverse the string and see if it’s the same as the original.” You can’t get much plainer than that.

Even more helpfully, Python’s [::-1] slicing syntax for reversing a string provides a convenient way to code it:

This is clear and concise. There’s hardly any need to look for an alternative. But just for fun, consider this recursive definition of a palindrome:

  • Base cases: An empty string and a string consisting of a single character are inherently palindromic.
  • Reductive recursion: A string of length two or greater is a palindrome if it satisfies both of these criteria:
    1. The first and last characters are the same.
    2. The substring between the first and last characters is a palindrome.

Slicing is your friend here as well. For a string word , indexing and slicing give the following substrings:

  • The first character is word[0] .
  • The last character is word[-1] .
  • The substring between the first and last characters is word[1:-1] .

So you can define is_palindrome() recursively like this:

It’s an interesting exercise to think recursively, even when it isn’t especially necessary.

Sort With Quicksort

The final example presented, like the nested list traversal, is a good example of a problem that very naturally suggests a recursive approach. The Quicksort algorithm is an efficient sorting algorithm developed by British computer scientist Tony Hoare in 1959.

Quicksort is a divide-and-conquer algorithm. Suppose you have a list of objects to sort. You start by choosing an item in the list, called the pivot item. This can be any item in the list. You then partition the list into two sublists based on the pivot item and recursively sort the sublists.

The steps of the algorithm are as follows:

  • Choose the pivot item.
  • Partition the list into two sublists:
    1. Those items that are less than the pivot item
    2. Those items that are greater than the pivot item
  • Quicksort the sublists recursively.

Each partitioning produces smaller sublists, so the algorithm is reductive. The base cases occur when the sublists are either empty or have one element, as these are inherently sorted.

Choosing the Pivot Item

The Quicksort algorithm will work no matter what item in the list is the pivot item. But some choices are better than others. Remember that when partitioning, two sublists that are created: one with items that are less than the pivot item and one with items that are greater than the pivot item. Ideally, the two sublists are of roughly equal length.

Imagine that your initial list to sort contains eight items. If each partitioning results in sublists of roughly equal length, then you can reach the base cases in three steps:

Optimal pivot item

Optimal Partitioning, Eight-Item List

At the other end of the spectrum, if your choice of pivot item is especially unlucky, each partition results in one sublist that contains all the original items except the pivot item and another sublist that is empty. In that case, it takes seven steps to reduce the list to the base cases:

Suboptimal pivot item

Suboptimal Partitioning, Eight-Item List

The Quicksort algorithm will be more efficient in the first case. But you’d need to know something in advance about the nature of the data you’re sorting in order to systematically choose optimal pivot items. In any case, there isn’t any one choice that will be the best for all cases. So if you’re writing a Quicksort function to handle the general case, the choice of pivot item is somewhat arbitrary.

The first item in the list is a common choice, as is the last item. These will work fine if the data in the list is fairly randomly distributed. However, if the data is already sorted, or even nearly so, then these will result in suboptimal partitioning like that shown above. To avoid this, some Quicksort algorithms choose the middle item in the list as the pivot item.

Another option is to find the median of the first, last, and middle items in the list and use that as the pivot item. This is the strategy used in the sample code below.

Implementing the Partitioning

Once you’ve chosen the pivot item, the next step is to partition the list. Again, the goal is to create two sublists, one containing the items that are less than the pivot item and the other containing those that are greater.

You could accomplish this directly in place. In other words, by swapping items, you could shuffle the items in the list around until the pivot item is in the middle, all the lesser items are to its left, and all the greater items are to its right. Then, when you Quicksort the sublists recursively, you’d pass the slices of the list to the left and right of the pivot item.

Alternately, you can use Python’s list manipulation capability to create new lists instead of operating on the original list in place. This is the approach taken in the code below. The algorithm is as follows:

  • Choose the pivot item using the median-of-three method described above.
  • Using the pivot item, create three sublists:
    1. The items in the original list that are less than the pivot item
    2. The pivot item itself
    3. The items in the original list that are greater than the pivot item
  • Recursively Quicksort lists 1 and 3.
  • Concatenate all three lists back together.

Note that this involves creating a third sublist that contains the pivot item itself. One advantage to this approach is that it smoothly handles the case where the pivot item appears in the list more than once. In that case, list 2 will have more than one element.

Using the Quicksort Implementation

Now that the groundwork is in place, you are ready to move on to the Quicksort algorithm. Here’s the Python code:

This is what each section of quicksort() is doing:

  • Line 4: The base cases where the list is either empty or has only a single element
  • Lines 7 to 13: Calculation of the pivot item by the median-of-three method
  • Lines 14 to 18: Creation of the three partition lists
  • Lines 20 to 24: Recursive sorting and reassembly of the partition lists

Note: This example has the advantage of being succinct and relatively readable. However, it isn’t the most efficient implementation. In particular, the creation of the partition lists on lines 14 to 18 involves iterating through the list three separate times, which isn’t optimal from the standpoint of execution time.

Here are some examples of quicksort() in action:

For testing purposes, you can define a short function that generates a list of random numbers between 1 and 100 :

Now you can use get_random_numbers() to test quicksort() :

To further understand how quicksort() works, see the diagram below. This shows the recursion sequence when sorting a twelve-element list:

Quicksort algorithm

Quicksort Algorithm, Twelve-Element List

In the first step, the first, middle, and last list values are 31 , 92 , and 28 , respectively. The median is 31 , so that becomes the pivot item. The first partition then consists of the following sublists:

Sublist Items
[18, 3, 18, 11, 28] The items less than the pivot item
[31] The pivot item itself
[72, 79, 92, 44, 56, 41] The items greater than the pivot item

Each sublist is subsequently partitioned recursively in the same manner until all the sublists either contain a single element or are empty. As the recursive calls return, the lists are reassembled in sorted order. Note that in the second-to-last step on the left, the pivot item 18 appears in the list twice, so the pivot item list has two elements.

Conclusion

That concludes your journey through recursion, a programming technique in which a function calls itself. Recursion isn’t by any means appropriate for every task. But some programming problems virtually cry out for it. In those situations, it’s a great technique to have at your disposal.

In this tutorial, you learned:

  • What it means for a function to call itself recursively
  • How the design of Python functions supports recursion
  • What factors to consider when choosing whether or not to solve a problem recursively
  • How to implement a recursive function in Python

You also saw several examples of recursive algorithms and compared them to corresponding non-recursive solutions.

You should now be in a good position to recognize when recursion is called for and be ready to use it confidently when it’s needed! If you want to explore more about recursion in Python, then check out Thinking Recursively in Python.

Get a short & sweet Python Trick delivered to your inbox every couple of days. No spam ever. Unsubscribe any time. Curated by the Real Python team.

Python Tricks Dictionary Merge

About John Sturtz

John is an avid Pythonista and a member of the Real Python tutorial team.

Each tutorial at Real Python is created by a team of developers so that it meets our high quality standards. The team members who worked on this tutorial are:

Что такое рекурсия в питоне

Напомним, что в математике факториал числа n определяется как Например, Ясно, что факториал можно легко посчитать, воспользовавшись циклом for. Представим, что нам нужно в нашей программе вычислять факториал разных чисел несколько раз (или в разных местах кода). Конечно, можно написать вычисление факториала один раз, а затем используя Copy-Paste вставить его везде, где это будет нужно.

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

Функции — это такие участки кода, которые изолированы от остальный программы и выполняются только тогда, когда вызываются. Вы уже встречались с функциями sqrt(), len() и print(). Они все обладают общим свойством: они могут принимать параметры (ноль, один или несколько), и они могут возвращать значение (хотя могут и не возвращать). Например, функция sqrt() принимает один параметр и возвращает значение (корень числа). Функция print() принимает переменное число параметров и ничего не возвращает.

Покажем, как написать функцию factorial(), которая принимает один параметр — число, и возвращает значение — факториал этого числа.

Дадим несколько объяснений. Во-первых, код функции должен размещаться в начале программы, вернее, до того места, где мы захотим воспользоваться функцией factorial(). Первая строчка этого примера является описанием нашей функции. factorial — идентификатор, то есть имя нашей функции. После идентификатора в круглых скобках идет список параметров, которые получает наша функция. Список состоит из перечисленных через запятую идентификаторов параметров. В нашем случае список состоит из одной величины n. В конце строки ставится двоеточие.

Далее идет тело функции, оформленное в виде блока, то есть с отступом. Внутри функции вычисляется значение факториала числа n и оно сохраняется в переменной res. Функция завершается инструкцией return res, которая завершает работу функции и возвращает значение переменной res.

Инструкция return может встречаться в произвольном месте функции, ее исполнение завершает работу функции и возвращает указанное значение в место вызова. Если функция не возвращает значения, то инструкция return используется без возвращаемого значения. В функциях, которым не нужно возвращать значения, инструкция return может отсутствовать.

Приведём ещё один пример. Напишем функцию max(), которая принимает два числа и возвращает максимальное из них (на самом деле, такая функция уже встроена в Питон).

Теперь можно написать функцию max3(), которая принимает три числа и возвращает максимальное их них.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *