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

Приветствую

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

Решение задачи:
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), но это условие возвращает единицу, а не число, возведенное в степень. Так каким же тогда образом выводится степень, а не единица?
  • Вопрос задан
  • 25407 просмотров
Решения вопроса 3
sergey-gornostaev
@sergey-gornostaev Куратор тега Python
Седой и строгий
Единица возвращается в предыдущий вызов функции, где умножается на 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:
                                #Эта ветка никогда не выполнится
                        )
                )
        )
)
Ответ написан
usdglander
@usdglander
Yipee-ki-yay
x^0 = 1.
В 7 классе изучается :)

upd: фактически алгоритм делает следующее (a * (a * (a * (a *....(a * 1)))))
Ответ написан
@abcd0x00
Как понять рекурсию в Python?

Нужно смотреть на функцию как на множество разных функций, похожих друг на друга. Поэтому когда функция вызывает саму себя, надо на это смотреть как на функцию, вызывающую очень похожую, но другую функцию. А когда функция вызывает другую функцию, они передают друг другу значения: вызывающая вызываемой подаёт параметры, а вызываемая вызывающей подаёт возвращаемое значение.
Ответ написан
Пригласить эксперта
Ответы на вопрос 4
EvilsInterrupt
@EvilsInterrupt
System programming, Reversing Engineering, C++
Прежде чем изучать рекурсию поймите сначала рекурсию.

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

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

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


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

Также, рекомендую почитать SICP. Эта книга дает ясное понимание между двумя нюансами по поводу рекурсии, о которых не каждый программист знает. Пример задачи : Напишите рекурсивную функцию вычисляющую факториал итеративно. Еще раз обращу внимание на формулировку: функция рекурсивная, а вычислить итеративно! Все это не бред и вполне логично, подробнее в SICP
Ответ написан
igorzakhar
@igorzakhar
В поиске работы python разработчика.
def listsum(numList):
   if len(numList) == 1:
        return numList[0]
   else:
        return numList[0] + listsum(numList[1:])

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

sumlistIn.pngsumlistOut.png
aliev.me/runestone/Recursion/CalculatingtheSumofaL...
Там, где примеры кода, нажмите кнопку "Show in Codelens" и можно пошагово посмотреть выполнение кода на python.
Ответ написан
@vashaaa
Юх с горы
А питон тут причем?) Рекурсия это рекурсия, это не плюшка какого либо языка, это математическое понятие. Она везде одинакова. В чем собственно проблема? Функция вызывает саму себя. В вашем случае она будет вызывать саму себя в самой себя(да звучит так себе), уменьшая переменную b(ваш степень) пока не будет верна проверка "if b == 0:".
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы