[Python] szybkie podnoszenie do potęgi

Question

Dzień dobry,

aktualnie uczę się Pythona i dla treningu postanowiłem napisać program rekurencyjnego szybkiego podnoszenia do potęgi. Podczas gdy algorytm działa bezproblemowo w C++, w Pythonie pojawia się błąd o treści "maximum recursion depth exceeded in comparison" . Bardzo prosiłbym o wytłumaczenie dlaczego tak się dzieje. Poniżej kod w obu językach.

def potega(x, n):
    if n == 1:
        return x
    else:
        p = potega(x, n / 2)
        if n % 2 == 1:
            return x * p * p
        else:
            return p * p


base = int(input("podaj podstawę: "))
power = int(input("podaj potęgę: "))
print(potega(base, power))

#include <iostream>

using namespace std;

long int potega(int x, int n)
{
    if(n==1) return x;
    else
    {
        long int p=potega(x, n/2);
        if(n%2==1) return x*p*p;
        else return p*p;
    }
}

int main()
{
    int x,n;
    cin>>x; cin>>n;
    cout<<potega(x,n);
    return 0;
}

 

Comments

szybkiego podnoszenia do potęgi

Jakby co, dla formalności (bo wiem że ten kod napisałeś w celach edukacyjnych) ale dodam: w Pythonie potęgowanie możesz zrobić `x**n` i to będzie szybsze od czegokolwiek co napiszesz z ręki ;)

---

Tak, zdaję sobie z tego sprawę, jednak w szkołach wciąż nas uczą takich rzeczy :P

Answer 1

Nie pokazałeś dla jakiego wejścia się tak dzieje, ale zakładam, że:

wypisz sobie wartość `n` w każdej iteracji rekursji (i na przyszłość, rób takie testy od razu ;D ). Zobaczysz pewnie liczby po przecinku? Tak więc powinieneś był użyć dzielenia całkowitego // zamiast dzielenia liczb rzeczywistych.

Comments

Dziękuję bardzo, uwagi zapamiętam.