Рекурсия

[cranxx]

Вычислить по следующему алгоритму: y=(x^n/2)^2 , если N чет-
ное; y=x*x^n-1 , если N нечетное.

Подскажите как реализовать? Разбирался с рекурсией на примере факториала вроде там все было ясно... А здесь не знаю.

[Granus]

int power(int x,int n){
    if(n==0)return 1;
    if(n%2==0){
        return power(x,n/2)*power(x,n/2);
    }else{
        return x*power(x,n-1);
    };
};

это без оптимизации и всего прочего

[ololo-schoolboy]

или так

int power(int x,int n){
    if(n==0) return 1;
    else if(n%2==0) return sqrt(power(x,n/2));
    else return x*power(x,n-1);
}