Функция которая вызывает сама себя: что это такое в программировании простыми словами

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

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

    

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

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

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!')

    

Скорость выполнения: итерация 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, то есть каждый последующий факториал включает в себя определение предыдущего.

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

12
    

Вывод:

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-го гармонического числа. Решите задачу итеративным и рекурсивным способами.

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

7
    

Вывод:

2.5928571428571425
    

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

def harmonic_iter(n):
    res = 0
    for i in  range(1, n + 1):
        res = 1 / i
    return res
print(harmonic_iter(int(input())))

    

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

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

    

Задание 4

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

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

9
    

Вывод:

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

    

Вывод:

3
    

Решение 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 – натуральное четное число.

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

120
    

Вывод:

3660
    

Решение 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('Такого числа нет в списке')

    

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

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

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

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

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

***

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

1. Особенности, сферы применения, установка, онлайн IDE
2. Все, что нужно для изучения Python с нуля – книги, сайты, каналы и курсы
3. Типы данных: преобразование и базовые операции
4. Методы работы со строками
5. Методы работы со списками и списковыми включениями
6. Методы работы со словарями и генераторами словарей
7. Методы работы с кортежами
8. Методы работы со множествами
9. Особенности цикла for
10. Условный цикл while
11. Функции с позиционными и именованными аргументами
12. Анонимные функции
13. Рекурсивные функции
14. Функции высшего порядка, замыкания и декораторы
    
15. Методы работы с файлами и файловой системой
    
16. Регулярные выражения
    
17. Основы скрапинга и парсинга
    

***

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

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

Как работает Рекурсия в Python — пример рекурсивной функции

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

• Рекурсивную функцию поиска факториала.
• Как рекурсивные функции работают в коде.
• Действительно ли рекурсивные функции выполняют свои задачи лучше итеративных?

Рекурсивные функции

Рекурсивная функция — это та, которая вызывает сама себя.

В качестве простейшего примера рассмотрите следующий код:

Копировать Скопировано Use a different Browser

def factorial_recursive(n):
if n == 1:
return n
else:
return n*factorial_recursive(n-1)

Вызывая рекурсивную функцию здесь и передавая ей целое число, вы получаете факториал этого числа (n!).

Вкратце о факториалах

Факториал числа — это число, умноженное на каждое предыдущее число вплоть до 1.

Например, факториал числа 7:
7! = 7*6*5*4*3*2*1 = 5040

Вывести факториал числа можно с помощью функции:

Копировать Скопировано Use a different Browser

num = 3
print(f"Факториал {num} это {factorial_recursive(num)}")

Эта функция выведет: «Факториал 3 это 6». Еще раз рассмотрим эту рекурсивную функцию:

def factorial_recursive(n):

    ...

По аналогии с обычной функцией имя рекурсивной указывается после def, а в скобках обозначается параметр n:

def factorial_recursive(n):
    if n == 1:
        return n
    else:
        return n*factorial_recursive(n-1)

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

def factorial_recursive(n):
    if n == 1:
        return n
    else:
        return n*factorial_recursive(n-1)

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

Это и есть рекурсия. В нашем примере это так сработало:

3 * (3-1) * ((3-1)-1)  # так как 3-1-1 равно 1, рекурсия остановилась

Детали работы рекурсивной функции

Чтобы еще лучше понять, как это работает, разобьем на этапы процесс выполнения функции с параметром 3.

Для этого ниже представим каждый экземпляр с реальными числами. Это поможет «отследить», что происходит при вызове одной функции со значением 3 в качестве аргумента:

Копировать Скопировано Use a different Browser

# Первый вызов
factorial_recursive(3):
if 3 == 1:
return 3
else:
return 3*factorial_recursive(3-1)
# Второй вызов
factorial_recursive(2):
if 2 == 1:
return 2
else:
return 2*factorial_recursive(2-1)
# Третий вызов
factorial_recursive(1):
if 1 == 1:
return 1
else:
return 1*factorial_recursive(1-1)

Рекурсивная функция не знает ответа для выражения 3*factorial_recursive(3–1), поэтому она добавляет в стек еще один вызов.

Как работает рекурсия

/\ factorial_recursive(1) - последний вызов
|| factorial_recursive(2) - второй вызов
|| factorial_recursive(3) - первый вызов

Выше показывается, как генерируется стек. Это происходит благодаря процессу LIFO (last in, first out, «последним пришел — первым ушел»). Как вы помните, первые вызовы функции не знают ответа, поэтому они добавляются в стек.

Но как только в стек добавляется вызов factorial_recursive(1), для которого ответ имеется, стек начинает «разворачиваться» в обратном порядке, выполняя все вычисления с реальными значениями. В процессе каждый из слоев выпадает в процессе.

• factorial_recursive(1) завершается, отправляет 1 в
• factorial_recursive(2) и выпадает из стека.
• factorial_recursive(2) завершается, отправляет 2*1 в
• factorial_recursive(3) и выпадает из стека. Наконец, инструкция else здесь завершается, возвращается 3 * 2 = 6, и из стека выпадает последний слой.

Рекурсия в Python имеет ограничение в 3000 слоев.

Копировать Скопировано Use a different Browser

>>> import sys
>>> sys.getrecursionlimit()
3000

Рекурсивно или итеративно?

Каковы же преимущества рекурсивных функций? Можно ли с помощью итеративных получить тот же результат? Когда лучше использовать одни, а когда — другие?

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

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

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

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

Копировать Скопировано Use a different Browser

def factorial_iterative(num):
factorial = 1
if num 
        print("Факториал не вычисляется для отрицательных чисел")
else:
for i in range (1, num + 1):
factorial = factorial*i
print(f"Факториал {num} это {factorial}")

рекурсия — Как возможно, что функция может вызывать сама себя

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

Давайте представим, как компилятор может превратить эту функцию в машинный код:

 (defun foo (x)
  (+ х (бар х)))
 

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

1. Он может скомпилировать foo таким образом, что вызов bar преобразуется в набор инструкций, которые говорят: «Найти определение функции, хранящееся под именем bar , каким бы оно ни было в данный момент, и организовать чтобы вызвать эту функцию с правильными аргументами».
2. Он может скомпилировать foo таким образом, что есть вызов функции машинного уровня для функции, но адрес этой функции оставлен как некий заполнитель. Затем он может прикрепить некоторые метаданные к foo в котором говорится: «перед вызовом этой функции вам нужно найти функцию с именем bar , найти ее адрес, вставить ее в код в нужном месте, и удалить эти метаданные .

Оба эти механизма позволяют определить foo до того, как станет известно, что такое bar . И обратите внимание, что вместо bar я мог бы написать foo : эти механизмы работают и с рекурсивными вызовами. Однако они отличаются не только этим.

• Первый механизм означает, что каждый раз, когда вызывается foo , необходимо выполнять какой-то динамический поиск bar , что повлечет за собой некоторые накладные расходы (но эти накладные расходы могут быть довольно небольшими):
  • вследствие этого первый механизм будет немного медленнее, чем мог бы быть;
  • , но также как следствие этого, если bar будет переопределено, то будет подхвачено новое определение, что очень желательно для интерактивного языка, которым обычно являются реализации Lisp.
• Второй механизм означает, что после того, как foo имеет все свои ссылки на другие функции, связанные с ним, вызовы происходят на машинном уровне:
  • это означает, что они будут быстры;
  • , но такое переопределение будет в лучшем случае более сложным, а в худшем вообще невозможным.

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

Очень простодушная система на Лиспе может работать исключительно по первому механизму (я почти уверен, что так работает, например, Python). Более продвинутый компилятор, вероятно, будет работать с комбинацией первого и второго механизма. Например, CL позволяет компилятору делать предположения о том, что кажущиеся вызовы самого себя в функциях действительно — это собственных вызовов, поэтому компилятор вполне может скомпилировать их как прямые вызовы (по сути, он скомпилирует функцию, а затем скомпонует ее на лету). Но при компиляции кода в целом он может вызывать «через имя» функции.

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

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

Могу ли я сам сделать вызов функции? — Новое для Юлии

marianoarnaiz 5 июля 2021 г. , 9:41

1

Всем привет.
Возможно, это ОЧЕНЬ глупый вопрос, но мне интересно, возможно ли это.

Я делаю эту функцию Set_Up(). Это дизайн для загрузки всех других функций в моем коде, принудительной предварительной компиляции, загрузки глобальных переменных и т. д.

Поскольку иногда что-то идет не так, у меня есть:

 попытка
Делать много вещей
поймать е
    printstyled("Произошла ошибка.",color=:red)
    printstyled("Пожалуйста, запустите Set_Up() еще раз.",color=:red)
    спать(1)
конец
 

Интересно, могу ли я внутри улова заставить функцию снова запуститься? Что-то вроде:

 попробовать
Делать много вещей
поймать е
    printstyled("Произошла ошибка.",color=:red)
    printstyled("Set_Up() снова запустится через 1 секунду.",color=:red)
    спать(1)
    Настраивать()
конец
 

Заранее спасибо!

где 5 июля 2021 г. , 10:15

2

Да. На самом деле я реализовал это для функции установления связи в сети несколько лет назад. У меня также была переменная «повторные попытки», которая увеличивается при каждом перезапуске, с возможностью выхода, если повторных попыток слишком много. Это предотвратило зависание функции слишком долго (на практике перезапуск почти никогда не происходил без сбоев в сети).

ваврин 5 июля 2021 г., 11:11

3

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

 функция привет()
  println("привет")
  привет()
конец
 

Но я думаю, здесь больше смысла искать причину, которая приводит к тому, что «что-то пошло не так».

сиджо 5 июля 2021 г., 11:19являюсь

4

Это называется рекурсией, важным методом в компьютерных науках. Обратите внимание, что каждый вызов размещается в стеке, поэтому, если вы зайдете слишком глубоко, вы получите переполнение стека (которое дало название известному веб-сайту).

 юлия> счетчик = 0;
юлия> функция f()
           глобальный счетчик += 1
           е()
       конец;
Юлия> ж()
ОШИБКА: StackOverflowError:
Трассировки стека:
 [1] ф()
   @ Основной ./REPL[12]:2
 [2] f() (повторяет 79980 раз)
   @ Основной ./REPL[12]:3
юлия> счетчик
130830
 

Итак, f смог рекурсивно вызвать себя 130830 раз, прежде чем стек стал слишком большим.

3 лайков

СтивенСью 5 июля 2021 г. , 11:30

5

номер:

Это называется рекурсией, важным методом в компьютерных науках. Обратите внимание, что каждый вызов размещается в стеке, поэтому, если вы зайдете слишком глубоко, вы получите переполнение стека (которое дало название известному веб-сайту).

Ну, не держите нас в напряжении вечно, как называется этот знаменитый сайт?

3 лайков

5 июля 2021 г., 11:52

6

Хм Привет, ребята.
Я пробовал это… но мой код просто зацикливается и никогда не завершается… Не знаю почему.
Интересно, есть ли строка для завершения текущего выполнения и повторного вызова функции.

Марианоарнаис 5 июля 2021 г. , 11:53

7

Проблема в том, что некоторые библиотеки в ОС нужно вызывать дважды (пакет GMT), чтобы они заработали. Это проблема пакета… и я не могу это исправить, хе-хе-хе.

кевбонэм 5 июля 2021 г., 12:12

8

Стивен Сью:

Ну, не держите нас в напряжении вечно, как называется этот знаменитый сайт?

Не могу сказать, шутит ли… https://stackoverflow.com/

2 лайка

рих 5 июля 2021 г., 14:46

9

При рекурсии в какой-то момент вы должны вернуть все, что не является вызовом функции, чтобы гарантировать завершение рекурсии. Вы делаете это с помощью условного выражения вроде «if counter > 100» и ничего не возвращаете в этом случае.

Для какого-то повторного звонка тоже можно использовать retry (из HTTP если не ошибаюсь)

Марианоарнаис 5 июля 2021 г., 19:05

10

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

Бернхард 5 июля 2021 г., 19:24

11

 функция myrecursion(depth::Int,arg)
    если глубина>=2
        ничего не возвращать
    еще
        println(аргумент)
        @info("моя рекурсия была вызвана (глубина=$(глубина))")
        вернуть мою рекурсию (глубина + 1, аргумент)
    конец
конец
моя рекурсия (0, "фу")
0
 

Стефан Карпински Разделить эту тему 5 июля 2021 г.