Уведомления

Группа в Telegram: присоединиться

#1 Окт. 9, 2017 17:19:21

Helseeret
Зарегистрирован: 2017-10-08
Сообщения: 5
Репутация: +  0  -
Профиль   Отправить e-mail  

Задача, понимающим рекурсию

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

 def func(n):
    if n < 1:
        return 1
    else:
        print(n)
        return func(n - 1)
func(10)

Офлайн

#2 Окт. 9, 2017 17:33:38

Rodegast
От: Пятигорск
Зарегистрирован: 2007-12-28
Сообщения: 2315
Репутация: +  169  -
Профиль   Отправить e-mail  

Задача, понимающим рекурсию

 >>> def foo(n, m=0):
...         if not n == m:
...             print m
...             return foo(n, m+1)
...         
>>> foo(5)
0
1
2
3
4



С дураками и сектантами не спорю, истину не ищу.
Ели кому-то правда не нравится, то заранее извиняюсь.

Офлайн

#3 Окт. 9, 2017 18:25:06

Helseeret
Зарегистрирован: 2017-10-08
Сообщения: 5
Репутация: +  0  -
Профиль   Отправить e-mail  

Задача, понимающим рекурсию

Так это два параметра в функции , а с одним можно как-то сделать и почему мы не описываем базовый случай или написав if not - если условие не выполнится, он автоматом вернет 0 и ничего прописывать не надо ? Не очень понимаю

Отредактировано Helseeret (Окт. 9, 2017 18:25:48)

Офлайн

#4 Окт. 9, 2017 19:36:00

Rodegast
От: Пятигорск
Зарегистрирован: 2007-12-28
Сообщения: 2315
Репутация: +  169  -
Профиль   Отправить e-mail  

Задача, понимающим рекурсию

> Так это два параметра в функции , а с одним можно как-то сделать

У функций может быть более 1 параметра. Не вижу в этом никакой проблемы.

> и почему мы не описываем базовый случай

Я тебе сам принцип показал. Остальное уже сам доделывай.



С дураками и сектантами не спорю, истину не ищу.
Ели кому-то правда не нравится, то заранее извиняюсь.

Офлайн

#5 Окт. 10, 2017 04:20:25

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 7025
Репутация: +  642  -
Профиль   Отправить e-mail  

Задача, понимающим рекурсию

Определение рекурсии
Разбор рекурсии
Разъяснение про дополнительный аргумент

  
>>> def func(n, prn=1):
...     if n > 0:
...         print(prn)
...         func(n - 1, prn + 1)
... 
>>> func(10)
1
2
3
4
5
6
7
8
9
10
>>>

tags: recursion



Отредактировано py.user.next (Окт. 27, 2017 10:56:29)

Офлайн

#6 Окт. 10, 2017 14:44:28

Shaman
Зарегистрирован: 2013-03-15
Сообщения: 1369
Репутация: +  88  -
Профиль   Отправить e-mail  

Задача, понимающим рекурсию

Helseeret
Не понимаю как эту задачу выполнить
Поменять местами вызов func с выводом.

  
def func(n):
    if n > 0:
        func(n - 1)
        print(n)

Офлайн

#7 Окт. 10, 2017 15:02:46

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 7025
Репутация: +  642  -
Профиль   Отправить e-mail  

Задача, понимающим рекурсию

Shaman
Поменять местами вызов func с выводом.
Выглядит просто, но не хвостовая, потому что сначала всё разматывается и кладётся в память. Рекурсивный вызов выполняется не последним в теле функции. Хотя в обычном питоне оно и не преобразуется в цикл, как в других языках.



Отредактировано py.user.next (Окт. 10, 2017 15:06:16)

Офлайн

#8 Окт. 10, 2017 15:08:14

Shaman
Зарегистрирован: 2013-03-15
Сообщения: 1369
Репутация: +  88  -
Профиль   Отправить e-mail  

Задача, понимающим рекурсию

py.user.next
сначала всё разматывается и кладётся в память
Тут же всё POC!

Офлайн

#9 Окт. 10, 2017 15:15:27

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 7025
Репутация: +  642  -
Профиль   Отправить e-mail  

Задача, понимающим рекурсию

Shaman
Тут же всё POC!
Хвостовая - ключевое слово.
wiki. хвостовая рекурсия



Отредактировано py.user.next (Окт. 10, 2017 15:17:16)

Офлайн

#10 Окт. 10, 2017 15:17:45

Shaman
Зарегистрирован: 2013-03-15
Сообщения: 1369
Репутация: +  88  -
Профиль   Отправить e-mail  

Задача, понимающим рекурсию

Shaman
Поменять местами вызов func с выводом.
Ключевые слова: “подъём” и “спуск”.

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version