Подскажите с кодом

@The Doctor · Регистрация: 31.05.2015

Студворк — интернет-сервис помощи студентам

Python
1
2
3
4
5
def f(x):
    if x == 1:
        return 2
    return f(x - 1) + 2
print(f(12))

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

Рыжий Лис · 19.01.2020, 17:22

Хвостовая рекурсия. Функция вызывает сама себя.

f(12) = f(11) + 2
f(11) = f(10) + 2
f(10) = f(9) + 2
f(9) = f(8) + 2
f(8) = f(7) + 2
f(7) = f(6) + 2
f(6) = f(5) + 2
f(5) = f(4) + 2
f(4) = f(3) + 2
f(3) = f(2) + 2
f(2) = f(1) + 2
f(1) = 2

И обратный ход рекурсии f(12) = 24.

@AlexMarkov · 19.01.2020, 17:42

The Doctor,

"Циклы могут ускорить работу программы. Рекурсия - работу программиста".

Каждая рекурсивная функция состоит из двух частей:
1 Базовый случай
2 Рекурсивный случай

Python
1
2
3
4
5
def f(x):
    if x == 1:  <-- базовый случай
        return 2
    return f(x - 1) + 2 <-- рекурсивный случай
print(f(12))

Если Вам не понятен пример приведенный Рыжим лисом:

1 Переходим на сайт http://pythontutor.com/visualize.html#mode=edit;
2 Вводим в предоставленную форму ваш код;
3 Нажимаем Visualize Execution
4 Нажимаем Next и смотрим, что происходит....
Если что-то не понятно, задаем вопрос повторно....

Хорошо алгоритм рекурсии написан в книге Бхаргава А "Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих"

Рыжий Лис · 19.01.2020, 17:47

Я бы сказал, что if x == 1: return 2 - это условие выхода из рекурсии, иначе программа зависнет.

@AlexMarkov · 19.01.2020, 18:07

Сообщение от Рыжий Лис

Я бы сказал, что if x == 1: return 2 - это условие выхода из рекурсии, иначе программа зависнет.

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

Добавлено через 9 минут
Самому Гвидо Ван Россуму, автору языка программирования Python не особо нравится прием основанный на алгоритме рекурсия, поэтому при разработке аппаратной части Python на применение данного алгоритма особого внимания не уделялось. Сам алгоритм следует знать в этом случае, а также частные случаи его применения. В пайтоне применяется редко.

Рыжий Лис · 19.01.2020, 18:11

Сообщение от AlexMarkov

В пайтоне применяется редко.

Ага, редко… Расскажите мне, как в будете обходить деревья или другие вложенные структуры без рекурсии.

Вот пример: Ошибка в вычислении арифм. выражения в виде дерева

@AlexMarkov · 19.01.2020, 18:22

Сообщение от Рыжий Лис

Ага, редко… Расскажите мне, как в будете обходить деревья или другие вложенные структуры без рекурсии.

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

Добавлено через 7 минут

Сообщение от Рыжий Лис

Вот пример: Ошибка в вычислении арифм. выражения в виде дерева

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

Рыжий Лис · 19.01.2020, 18:24

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

Добавлено через 1 минуту

Сообщение от AlexMarkov

Т.е. иногда необходимо искать ответ в самом вопросе.

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

@AlexMarkov · 19.01.2020, 18:34

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

Рыжий Лис · 19.01.2020, 18:43

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

https://ru.wikipedia.org/w/ind... =101801083

В том случае дерево строилось так:

Python
1
2
3
4
5
6
class Node:
    def __init__(self, data, left=None, right=None):
        print(f'new node "{data}"')
        self.data = data
        self.left = left     # левое поддерево
        self.right = right  # правое поддерево

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

Добавлено через 2 минуты

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

https://ru.wikipedia.org/w/ind... =101110086

@AlexMarkov · 19.01.2020, 19:15

Сообщение от Рыжий Лис

эмулирующая древовидную структуру

т.е. не является самой древовидной структурой.
Решение этого вопроса за рамками раздела форума python для начинающих. У меня еще не достаточно опыта для правильного ответа на этот вопрос.
Необходима проработка материала касательно пространственно - древовидной структуры. Я зависаю....

Добавлено через 3 минуты
Надо читать главу 10 Хайнеман, Джордж, Пояяис, Гэри, Сеяков, Стэнли. Алгоритмы. Справочник с примерами на С, C++, Java и Python.
Пространственно-древовидные структуры. Да и зачем этот вопрос? Чтобы оценить мой уровень знаний в программировании? Я в разделе python для начинающих.... могу себе позволить...

Рыжий Лис · 19.01.2020, 19:22

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

@AlexMarkov · 19.01.2020, 19:28

Сообщение от AlexMarkov

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

Загрузка...Простите...Загрузка....

Сообщение от AlexMarkov

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

Новые блоги и статьи Все статьи Все блоги /
Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025

Рыжий Лис Просто Лис 5972 / 3734 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	19.01.2020, 17:22
	Сообщение было отмечено The Doctor как решение Решение Хвостовая рекурсия. Функция вызывает сама себя. f(12) = f(11) + 2 f(11) = f(10) + 2 f(10) = f(9) + 2 f(9) = f(8) + 2 f(8) = f(7) + 2 f(7) = f(6) + 2 f(6) = f(5) + 2 f(5) = f(4) + 2 f(4) = f(3) + 2 f(3) = f(2) + 2 f(2) = f(1) + 2 f(1) = 2 И обратный ход рекурсии f(12) = 24. 1

Рыжий Лис Просто Лис 5972 / 3734 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	19.01.2020, 17:47
	Я бы сказал, что `if x == 1: return 2` - это условие выхода из рекурсии, иначе программа зависнет. 0

@AlexMarkov 99 / 86 / 20 Регистрация: 10.09.2019 Сообщений: 708
	19.01.2020, 18:34
	Надо знать, что автор сам подразумевал под словом "дерево". Да и сам вопрос вырван из общего контекста книги, необходима информация в полном объеме. 0

Рыжий Лис Просто Лис 5972 / 3734 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	19.01.2020, 19:22
	Вы сказали, что рекурсия не нужна, я привёл контрпример. 2