DjangoBB LoFi version

Полная версия: Задача, понимающим рекурсию

Начало » Python для экспертов » Задача, понимающим рекурсию

1 2

Helseeret

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

Для начала, как я понимаю, в каждой рекурсивной функции т.е каждый раз когда функция вызывает саму себя сохраняются переменные этой функции т.е используя рекурсию у нас на каждом вызове функции будут разные переменные, и выполняться будет она до базового случая, а как она дойдет до базового случая она будет идти в обратном порядке, используя значения верх лежащей функции (если рассматривать стек, как кувшин, в котором последней зашедшей предмет будет выходить первым) для вычисления низ лежайшей функции и так до тех пор пока не дойдет до самой первой вызванной функции.
Так вот задача звучит так вывести рекурсивно числа от 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)

Rodegast

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

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

Helseeret

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

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

Rodegast

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

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

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

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

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

py.user.next

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

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

  
>>> 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

Shaman

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

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

Поменять местами вызов func с выводом.

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

py.user.next

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

Shaman
Поменять местами вызов func с выводом.

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

Shaman

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

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

Тут же всё POC!

py.user.next

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

Shaman
Тут же всё POC!

Хвостовая - ключевое слово.
wiki. хвостовая рекурсия

Shaman

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

Shaman
Поменять местами вызов func с выводом.

Ключевые слова: “подъём” и “спуск”.