natkaida 23 января 2023

Python

43108

🐍 Самоучитель по Python для начинающих. Часть 13: Рекурсивные функции

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

← Часть 12

Анонимные функции

Часть 14 →

Функции высшего порядка, замыкания и декораторы

Рекурсивная функция – это функция, которая вызывает сама себя, и при каждом очередном вызове использует данные, созданные во время предыдущего вызова. В программировании есть ряд задач, которые проще (но не всегда эффективнее) решаются с помощью рекурсии. Написание рекурсивных функций часто ставит начинающих программистов в тупик. Чтобы разобраться в принципе работы рекурсивных функций, нужно понять (в самых общих чертах) концепцию стека вызовов.

Стек – это структура данных LIFO (last in, first out): информация последовательно добавляется в «стопку» , каждый новый объект помещается поверх предыдущего, а извлекаются объекты в обратном порядке, – начиная с верхнего. Работу стека отлично иллюстрирует добавление данных в список с помощью append и извлечение информации посредством pop:

stack = []
for i in range(1, 11):
    stack.append(f'{i}-й элемент')
    print(f'+ {i}-й элемент добавлен')
    for i in stack:
        print(i, end=" ")
print('\n')    
for i in range(len(stack)):
    print('В стеке: ', end=" ")
    for i in stack:
        print(i, end=" ")
    print(f'\n{stack.pop()} удален из стека')

Вывод:

+ 1-й элемент добавлен
1-й элемент + 2-й элемент добавлен
1-й элемент 2-й элемент + 3-й элемент добавлен
1-й элемент 2-й элемент 3-й элемент + 4-й элемент добавлен
1-й элемент 2-й элемент 3-й элемент 4-й элемент + 5-й элемент добавлен
1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент + 6-й элемент добавлен
1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент + 7-й элемент добавлен
1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент 7-й элемент + 8-й элемент добавлен
1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент 7-й элемент 8-й элемент + 9-й элемент добавлен
1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент 7-й элемент 8-й элемент 9-й элемент + 10-й элемент добавлен
1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент 7-й элемент 8-й элемент 9-й элемент 10-й элемент 

В стеке:  1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент 7-й элемент 8-й элемент 9-й элемент 10-й элемент 
10-й элемент удален из стека
В стеке:  1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент 7-й элемент 8-й элемент 9-й элемент 
9-й элемент удален из стека
В стеке:  1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент 7-й элемент 8-й элемент 
8-й элемент удален из стека
В стеке:  1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент 7-й элемент 
7-й элемент удален из стека
В стеке:  1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент 
6-й элемент удален из стека
В стеке:  1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 
5-й элемент удален из стека
В стеке:  1-й элемент 2-й элемент 3-й элемент 4-й элемент 
4-й элемент удален из стека
В стеке:  1-й элемент 2-й элемент 3-й элемент 
3-й элемент удален из стека
В стеке:  1-й элемент 2-й элемент 
2-й элемент удален из стека
В стеке:  1-й элемент 
1-й элемент удален из стека

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

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

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

Программисту не нужно беспокоиться о работе стека вызовов – созданием фреймов и управлением стеком занимается интерпретатор. Однако понимание принципа работы стека вызовов значительно упрощает создание рекурсивных функций. Неверное же использование рекурсии приводит к переполнению стека (stack overflow). Популярный сайт StackOverflow назван как раз в честь этой ошибки.

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

def recursive():
    recursive()

recursive()

Интерпретатор Python автоматически отслеживает переполнение стека и после 1000 бесплодных вызовов завершает работу подобных функций с ошибкой:

shortest()
RecursionError: maximum recursion depth exceeded

При желании лимит на глубину рекурсии можно увеличить, но сделать его бесконечным, разумеется, нельзя – даже самый внушительный объем оперативной памяти в итоге окажется переполненным:

from sys import getrecursionlimit
from sys import setrecursionlimit
print(getrecursionlimit()) # выводит лимит по умолчанию
setrecursionlimit(2000) # увеличивает лимит до 2000 вызовов
print(getrecursionlimit())# выводит новый лимит

#Вывод:
1000
2000

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

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

Вот пример простейшей рекурсивной функции, в которой учтены оба случая:

def greetings(st):
     print(st)
     if len(st) == 0:  # Граничный случай
         return             
     else:       # Рекурсивный случай
         greetings(st[:-1])   

greetings('Hello, world!')

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

Hello, world!
Hello, world
Hello, worl
Hello, wor
Hello, wo
Hello, w
Hello, 
Hello,
Hello
Hell
Hel
He
H

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

def greetings(st):
    print(st)
    if len(st) > 0:  
        greetings(st[:-1])   

greetings('Hello world!')

И в первом, и во втором варианте рекурсивный случай многократно передает в функцию greetings() подстроку, длина которой уменьшается с каждым вызовом, пока не станет равной 0.

🐍🎓 Библиотека собеса по Python

Подтянуть свои знания по Python вы можете на нашем телеграм-канале «Библиотека собеса по Python»

🐍🧩 Библиотека задач по Python

Интересные задачи по Python для практики можно найти на нашем телеграм-канале «Библиотека задач по Python»

Скорость выполнения: итерация vs рекурсия

Рекурсивные функции работают медленнее обычных, поэтому их стоит применять только тогда, когда решить задачу без рекурсии сложно. Вот сравнение времени выполнения двух функций, рекурсивной fib_recursive(n) и обычной fib_iter(n), решающих одну и ту же задачу – вычисление последовательности Фибоначчи:

from timeit import timeit

def fib_iter(n):
    if n == 1:
        return [1]
    if n == 2:
        return [1, 1]
    fibs = [1, 1]
    for _ in range(2, n):
        fibs.append(fibs[-1] + fibs[-2])
    return fibs

setup_code_iter = 'from __main__ import fib_iter'
stmt_iter = 'fib_iter(15)'
print('Время выполнения итеративной функции: ', timeit(setup=setup_code_iter, stmt=stmt_iter, number=20000))

def fib_recursive(n):
    if(n <= 1):
        return n
    else:
        return(fib_recursive(n-1) + fib_recursive(n-2))
    
setup_code_rec = 'from __main__ import fib_recursive'
stmt_rec = 'fib_recursive(15)'
print('Время выполнения рекурсивной функции: ', timeit(setup=setup_code_rec, stmt=stmt_rec, number=20000))

Результат для n = 15:

Время выполнения итеративной функции:  0.034556168131530285
Время выполнения рекурсивной функции:  4.069674882106483

В приведенном выше примере в обычной функции используется цикл for. Цикл выполняет итерацию (перебор), причем справляется с задачей гораздо быстрее, чем рекурсивная функция, поскольку рекурсия совершает множество повторных вызовов, и с увеличением числа элементов последовательности количество повторов растет лавинообразно:

Рекурсивные вызовы при вычислении ряда Фибоначчи

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

Мемоизация

Если применение рекурсии при решении задачи неизбежно, есть простой способ ускорить выполнение функции – для этого используют декоратор @lru_cache() модуля functools. Сравним скорость выполнения рекурсивного кода при решении следующей олимпиадной задачи.

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

Лесенка состоит из нескольких рядов кубиков

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

from timeit import timeit

def kol_les_no_mem(n, k):
    if n == 0:
        return 1
    ans = 0
      
    for i in range(k + 1, n + 1):
        ans += kol_les_no_mem(n - i,  i)
    return ans

setup_code_no_mem = 'from __main__ import kol_les_no_mem'
stmt_no_mem = 'kol_les_no_mem(25, 0)'
print('Время выполнения без мемоизации: ', timeit(setup=setup_code_no_mem, stmt=stmt_no_mem, number=20000))

setup_code_mem = '''
import functools
@functools.lru_cache(maxsize=None)

def kol_les_mem(n, k):
    if n == 0:
        return 1
    ans = 0
      
    for i in range(k + 1, n + 1):
        ans += kol_les_mem(n - i,  i)
    return ans
'''

stmt_mem = 'kol_les_mem(25, 0)'
print('Время выполнения с мемоизацией: ', timeit(setup=setup_code_mem, stmt=stmt_mem, number=20000))

Результат теста:

Время выполнения без мемоизации:  9.019254605285823
Время выполнения с мемоизацией:  0.0023915572091937065

Практика

Задание 1

Напишите функцию для вычисления факториала числа. Решите задачу двумя способами – итеративным и рекурсивным.

Примечание для рекурсивного решения: предположим, нам нужно вычислить 5! Факториал 5 равен: 5 х 4 х 3 х 2 х 1. Факториал 4: 4 х 3 х 2 х 1, факториал 3: 3 х 2 х 1, факториал 2: 2 х 1, и факториал 1 равен 1. Очевидно, что 5! = 5 x 4!, 4! = 4 x 3!, 3! = 3 x 2! и так далее до граничного случая 1! = 1, то есть каждый последующий факториал включает в себя определение предыдущего.

Пример ввода:

Вывод:

479001600

Решение 1 – итеративное:

def fact_iter(n):
    factorial = 1
    for i in range(1, n + 1):
        factorial *= i
    return factorial
print(fact_iter(int(input())))

Решение 2 – рекурсивное:

def fact_recursive(n):
    if n == 1: # граничный случай
        return 1
    else: # рекурсивный случай
        return n * fact_recursive(n - 1)
print(fact_recursive(int(input())))

Задание 2

Напишите программу для возведения числа n в степень m. Решите задачу двумя способами – итеративным и рекурсивным.

Примечание для рекурсивного решения: предположим, что нужно возвести число 5 в степень 6. Свойства степени позволяют разбить процесс на более мелкие операции и представить выражение 5 ** 6 в виде (5 ** 3) ** 2. Этот подход работает в том случае, если степень представляет собой четное число. Если степень нечетная, следует воспользоваться другим свойством: (n ** m) x n = n ** (m + 1). Поскольку может ввести как четное, так и нечетное значение m, в функции должны быть два рекурсивных случая. В качестве граничного случая используется еще одно свойство степени: n ** 1 = n.

Пример ввода:

12
8

Вывод:

429981696

Решение 1 – итеративное:

def pow_iter(n, m):
    res = 1
    for i in range(m):
        res *= n
    return res
n, m = int(input()), int(input())
print(pow_iter(n, m))

Решение 2 – рекурсивное:

def pow_recursive(n, m):
    if m == 1: # граничный случай
        return n
    elif m % 2 == 0: # четный рекурсивный случай
        res = pow_recursive(n, m // 2)
        return res * res
    else: # нечетный рекурсивный случай
        res = pow_recursive(n, m // 2)
        return res * res * n
n, m = int(input()), int(input())
print(pow_recursive(n, m))

Задание 3

Напишите программу для нахождения n-го гармонического числа. Решите задачу итеративным и рекурсивным способами.

Пример ввода:

Вывод:

2.5928571428571425

Решение 1 – итеративное:

def nth_harmonic_iter(n):
    harmonic = 1.0
    for i in range(2, n + 1):
        harmonic += 1 / i
    return harmonic
print(round(nth_harmonic_iter(int(input())), 5))

Решение 2 – рекурсивное:

def nth_harmonic_rec(n):
    if n == 1: #граничный случай
        return 1
    else: #рекурсивный случай
        return 1 / n + nth_harmonic_rec(n - 1)
print(round(nth_harmonic_rec(int(input())), 5))

Задание 4

Напишите итеративную и рекурсивную функции для вычисления суммы n первых членов геометрической прогрессии:

Прогрессия

Пример ввода:

Вывод:

1.99609375

Решение 1 – итеративное:

def geometric_iter(n):
    res = 0
    for i in range(n):
        res += 1 / 2 ** i
    return res    
print(geometric_iter(int(input())))

Решение 2 – рекурсивное:

def geometric_rec(n):
   if n < 0: # граничный случай
       return 0
   else: # рекурсивный случай
       return 1 / 2 ** n + geometric_rec(n - 1)
print(geometric_rec(int(input())))

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

b, q, n = 1, 0.5, int(input())
print(b * (1 - q ** n) / (1 - q))

Задание 5

Напишите рекурсивную и итеративную функции для вычисления наибольшего общего делителя чисел a и b.

Пример ввода:

45
123

Вывод:

Решение 1 – рекурсивное:

def gcd_recursive(a, b):
    min_num = min(a, b)
    max_num = max(a, b)

    if min_num == 0: #граничный случай, когда одно из чисел равно 0
        return max_num
    elif min_num == 1: #граничный случай, когда одно из чисел равно 1
        return 1
    else: #рекурсивный случай, когда ни одно из чисел не равно ни 1, ни 0
        return gcd_recursive(min_num, max_num % min_num)
a, b = int(input()), int(input())
print(gcd_recursive(a, b))

Решение 2 – итеративное:

def gcd_iter(a, b):
    while a != b:
        if a > b:
            a -= b
        else:
            b -= a
    return b        
a, b = int(input()), int(input())
print(gcd_iter(a, b))

Примечание: задачу можно решить с помощью math.gcd():

import math
a, b = int(input()), int(input())
print(math.gcd(a, b))

Задание 6

Напишите итеративную и рекурсивную функции для вычисления последовательности n + (n – 2) + (n – 4)... (n – x =< 0), где n – натуральное четное число.

Пример ввода:

Вывод:

Решение 1 – итеративное:

def sum_iter(n):
    summa = 0
    k = 0
    while n - k > 0:
        summa += n - k 
        k += 2
    return summa    
print(sum_iter(int(input())))

Решение 2 – рекурсивное:

def sum_recursive(n):
    if n < 1: # граничный случай
        return 0
    else: # рекурсивный случай
        return n + sum_recursive(n - 2)
        
print(sum_recursive(int(input())))

Задание 7

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

Пример ввода:

Лёша на полке клопа нашёл

Вывод:

True

Решение:

def palindrome(my_str):
    if len(my_str) == 0 or len(my_str) == 1: # граничный случай
        return True
    else: # рекурсивный случай
        head = my_str[0]
        middle = my_str[1:-1]
        end = my_str[-1]
        return head == end and palindrome(middle)

st = [i.lower() for i in input() if i.isalpha()]
print((palindrome(st)))

Без рекурсии задачу можно решить так:

st = [i.lower() for i in input() if i.isalpha()]
print(st == st[::-1])

Задание 8

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

Родословная

Вывод:

Посещаем узел Анна...
Проверяем, состоит ли имя Анна из 9 букв...
Посещаем узел Егор...
Проверяем, состоит ли имя Егор из 9 букв...
Посещаем узел Мария...
Проверяем, состоит ли имя Мария из 9 букв...
Посещаем узел Светлана...
Проверяем, состоит ли имя Светлана из 9 букв...
Посещаем узел Инга...
Проверяем, состоит ли имя Инга из 9 букв...
Посещаем узел Елизавета...
Проверяем, состоит ли имя Елизавета из 9 букв...
Имя из 9 букв: Елизавета

Решение:

root = {'name': 'Анна', 'children': [{'name': 'Егор', 'children':
[{'name': 'Мария', 'children': []}]}, {'name': 'Светлана',
'children': [{'name': 'Инга', 'children': [{'name': 'Елизавета',
'children': []}, {'name': 'Антон', 'children': []}]}, {'name': 'Марина', 'children': []}]}]}

def find_name(node):
    print(f"Посещаем узел {node['name']}...")
    print(f"Проверяем, состоит ли имя {node['name']} из 9 букв...")
    if len(node['name']) == 9: 
        return node['name'] # граничный случай

    if len(node['children']) > 0:  # рекурсивный случай
        for child in node['children']:
            returnValue = find_name(child)
            if returnValue != 'не найдено':
                return returnValue

    return 'не найдено' # граничный случай - имен из 9 букв нет

print(f"Имя из 9 букв: {find_name(root)}")

Примечание: без рекурсии такую задачу можно решить с помощью ООП:

class Node:
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def traverse(root):
    if root is None:
        return

    traverse(root.left)
    if len(root.data) == 9:
        print(f'Имя найдено: {root.data}')
        return
 
    traverse(root.right)
    if len(root.data) == 9:
        print(f'Имя найдено: {root.data}')
        return

 
if __name__ == '__main__':
    root = Node('Анна')
    root.left = Node('Егор')
    root.right = Node('Светлана')
    root.left.left = Node('Мария')
    root.right.left = Node('Инга')
    root.right.right = Node('Марина')
    root.right.left.left = Node('Елизавета')
    root.right.left.right = Node('Антон')
 
    traverse(root)

Задание 9

Имеется многомерный вложенный список:

sp = [[[5, 7, 2], [4, 9, 5]], [[2, 5, 4]], [[3, 2, 1], [[5], [9, 5]]],
      [4, 3, 1, 2], [[4, 7, 2], [6, 4]], [[[4, 1, 6], [3, 8]], [4, 5]],
      [9, 1], [3, 1], [[5, 6], [[4, 2, 1], [2, 5], [[6, 8, 2, 3, 4]]]],
      [5, 3, 2], [2, [1], 4], [2, 5, [4, 3, 1], 6, 7, [9, 0, 5, 2, 4]],
      [7, 3, [4]], [4, 2, [[[5, 6, 7], 5, 7]], 1], [3, 4, 6, [6, 4, 5]],
     ]

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

Ожидаемый результат:

[5, 7, 2, 4, 9, 5, 2, 5, 4, 3, 2, 1, 5, 9, 5, 4, 3, 1, 2, 4, 7, 2, 6, 4, 4, 1, 6, 3, 8, 4, 5, 9, 1, 3, 1, 5, 6, 4, 2, 1, 2, 5, 6, 8, 2, 3, 4, 5, 3, 2, 2, 1, 4, 2, 5, 4, 3, 1, 6, 7, 9, 0, 5, 2, 4, 7, 3, 4, 4, 2, 5, 6, 7, 5, 7, 1, 3, 4, 6, 6, 4, 5]

Решение 1 – рекурсивное:

def flat_list_recur(lst):
    if lst == []:
        return lst
    if isinstance(lst[0], list):
        return flat_list_recur(lst[0]) + flat_list_recur(lst[1:])
    return lst[:1] + flat_list_recur(lst[1:])

sp = [[[5, 7, 2], [4, 9, 5]], [[2, 5, 4]], [[3, 2, 1], [[5], [9, 5]]],
      [4, 3, 1, 2], [[4, 7, 2], [6, 4]], [[[4, 1, 6], [3, 8]], [4, 5]],
      [9, 1], [3, 1], [[5, 6], [[4, 2, 1], [2, 5], [[6, 8, 2, 3, 4]]]],
      [5, 3, 2], [2, [1], 4], [2, 5, [4, 3, 1], 6, 7, [9, 0, 5, 2, 4]],
      [7, 3, [4]], [4, 2, [[[5, 6, 7], 5, 7]], 1], [3, 4, 6, [6, 4, 5]],
     ]
print(flat_list_recur(sp))

Решение 2 – итеративное:

def flat_list_iter(lst):
    result = []
    stack = [lst]
    while stack:
        current = stack.pop(-1)
        if isinstance(current, list):
            stack.extend(current)
        else:
            result.append(current)
    result.reverse() 
    return result

sp = [[[5, 7, 2], [4, 9, 5]], [[2, 5, 4]], [[3, 2, 1], [[5], [9, 5]]],
      [4, 3, 1, 2], [[4, 7, 2], [6, 4]], [[[4, 1, 6], [3, 8]], [4, 5]],
      [9, 1], [3, 1], [[5, 6], [[4, 2, 1], [2, 5], [[6, 8, 2, 3, 4]]]],
      [5, 3, 2], [2, [1], 4], [2, 5, [4, 3, 1], 6, 7, [9, 0, 5, 2, 4]],
      [7, 3, [4]], [4, 2, [[[5, 6, 7], 5, 7]], 1], [3, 4, 6, [6, 4, 5]],
     ]

print(flat_list_iter(sp))

Задание 10

Реализуйте алгоритм бинарного поиска с помощью итеративной и рекурсивной функций. Число задается с помощью randrange(2000), в списке хранятся числа от 1 до 1000, т.е. не во всех случаях заданное число будет присутствовать в списке.

Пример вывода:

Число найдено: 787

Решение 1 – рекурсивное:

from random import randrange

def binary_recursive(lst, start, end, num):
    if end >= start:  
        mid = (end + start) // 2
        if lst[mid] == num: # граничный случай - элемент находится посередине
            return mid
        
        elif lst[mid] > num: # рекурсивный случай - элемент находится слева
            return binary_recursive(lst, start, mid - 1, num)

        else: # рекурсивный случай - элемент находится справа
            return binary_recursive(lst, mid + 1, end, num)

    else: # граничный случай - элемент в списке не обнаружен
         return 'не найдено'

sp = [i for i in range(1001)]
n = randrange(2000)

result = binary_recursive(sp, 0, len(sp)-1, n)

if result != 'не найдено':
    print(f'Число найдено: {result}')
else:
    print('Такого числа нет в списке')

Решение 2 – итеративное:

from random import randrange

def binary_iter(lst, num):
    start, end, mid = 0, len(lst) - 1, 0

    while start <= end:
        mid = (end + start) // 2
        if lst[mid] < num:
            start = mid + 1
        elif lst[mid] > num:
            end = mid - 1
        else:
            return mid
    return 'не найдено'

sp = [i for i in range(1001)]
n = randrange(2000)

result = binary_iter(sp, n)

if result != 'не найдено':
    print(f'Число найдено: {result}')
else:
    print('Такого числа нет в списке')

Подведем итоги

Рекурсию стоит применять для решения задач, в которых:

Используется древовидная структура данных.
Нужно предусмотреть возврат к предыдущей отправной точке (например, при поиске выхода из лабиринта).
Глубина рекурсивных вызовов находится в пределах разумного и не приведет к переполнению стека.

Во всех остальных случаях целесообразнее использовать итерацию либо итерацию и стек.

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

***

Содержание самоучителя

***

🐍 Библиотека питониста

Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека питониста»

Интересно, перейти к каналу

🐍 Самоучитель по Python для начинающих. Часть 13: Рекурсивные функции

Скорость выполнения: итерация vs рекурсия

Мемоизация

Практика

Задание 1

Задание 2

Задание 3

Задание 4

Задание 5

Задание 6

Задание 7

Задание 8

Задание 9

Задание 10

Подведем итоги

Содержание самоучителя

ВАКАНСИИ

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ

ООП на Python: концепции, принципы и примеры реализации

3 самых важных сферы применения Python: возможности языка

Программирование на Python: от новичка до профессионала