Как понять рекурсию в Python?

Question

[weranda]

Приветствую

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

Решение задачи:

def rec(a,b):
    if b == 0:
        return 1
    else:
        return a * rec(a, b-1)

a, b = 2, 3
print(rec(a,b))

В функции в условии else а вычисляется до нужной степени, с каждой рекурсией b уменьшается на единицу и в итоге приравнивается к нулю. Когда b равно нулю выполняется первое условие (return 1), но это условие возвращает единицу, а не число, возведенное в степень. Так каким же тогда образом выводится степень, а не единица?

Comments

[Lander]

Вспомнилось: Чтобы понять рекурсию, нужно понять рекурсию!

Answer 1

[Сергей Горностаев]

Единица возвращается в предыдущий вызов функции, где умножается на a равную двум и опять возвращается в предудщий вызов. Так пока не дойдёт до первого вызова, который вернёт значение своё функции print(). Чтобы лучше представить это, мыслено замени вызовы функции на её тело

(
    if 3 == 0:
        return 1
    else:
        return 2 * (
            if 2 == 0:
                return 1
            else:
                return 2 * (
                    if 1 == 0:
                        return 1
                    else:
                        return 2 *  (
                            if 0 == 0:
                                return 1
                            else:
                                #Эта ветка никогда не выполнится
                        )
                )
        )
)

Answer 2

[Lander]

x^0 = 1.
В 7 классе изучается :)

upd: фактически алгоритм делает следующее (a * (a * (a * (a *....(a * 1)))))

Comments

[weranda]

Я не могу понять рекурсию, а вы про степени мне рассказываете. Смысл?

[Сергей Кузьмин]

weranda: вам объяснили как работает эта рекурсия. Что вы не поняли?

[Павел]

Чтобы понять рекурсию, надо понять рекурсию.

Answer 3

[abcd0x00]

Как понять рекурсию в Python?

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

Comments

[MikeLebedev]

Спасибо тебе огромное, добрый умный человек!

Answer 4

[3dr1aN]

Как понять рекурсию в Python?
здесь есть ответ

Comments

[Даниил Демидко]

Вот, он путь к просветлению)

Answer 5

[Дмитрий]

Прежде чем изучать рекурсию поймите сначала рекурсию.

Рекурсия это способ решения задачи путем ее упрощения до такого состояния, когда задачу уже можно взять и решить, а не упрощать.

Вам уже привели пример со степенью:
2 ^ 2
Известно что если упростить до:
2 ^ 0 , то мы должны получить результат 1
Вот и упрощайтее задачу возведения в степень до того, чтобы текущий показатель степени стал равным 0.

def pow(num, n2):
1 if n2 == 0 else num * pow(num, n2-1)

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

Также, рекомендую почитать SICP. Эта книга дает ясное понимание между двумя нюансами по поводу рекурсии, о которых не каждый программист знает. Пример задачи : Напишите рекурсивную функцию вычисляющую факториал итеративно. Еще раз обращу внимание на формулировку: функция рекурсивная, а вычислить итеративно! Все это не бред и вполне логично, подробнее в SICP

Answer 6

[igorzakhar]

def listsum(numList):
   if len(numList) == 1:
        return numList[0]
   else:
        return numList[0] + listsum(numList[1:])

print(listsum([1,3,5,7,9]))

aliev.me/runestone/Recursion/CalculatingtheSumofaL...
Там, где примеры кода, нажмите кнопку "Show in Codelens" и можно пошагово посмотреть выполнение кода на python.

Answer 7

[Mr Hobot]

А питон тут причем?) Рекурсия это рекурсия, это не плюшка какого либо языка, это математическое понятие. Она везде одинакова. В чем собственно проблема? Функция вызывает саму себя. В вашем случае она будет вызывать саму себя в самой себя(да звучит так себе), уменьшая переменную b(ваш степень) пока не будет верна проверка "if b == 0:".