Рекурсивная функция возведения в степень

@Fatallol · Регистрация: 17.10.2014

Author24 — интернет-сервис помощи студентам

Мое задание: Вычислить y = x^n(икс в степени n) по следующему правилу: y = ( x^n/2 )^2, если n четное и y = x * y^(n–1), если n нечетное. Без рекурсии я сделал, а как с рекурсией? Я понятия не имею, помогите пожалуйста.Чего в интернете только не прочитал, все про факториал, а в моем примере не могу, хоть убейте.
Сам пишу в оконном, но можно и в консоли. Я пойму. Вот мой кусочек кода без рекурсии:

C++

double Fun(int n, double x)  {
double y;
if(n%2==0)
y=x*pow(x,n-1); // думал, что ошибка в условии. Заменил y из условия на x.
else
y=pow(pow(x,n/2),2);
return y;
}

@saden · 23.02.2015, 15:24

C++

double pow(double x, int n)
{if(n==0) return 1;
 if(n==1) return x;
 if(n&1) return x*pow(x,n/2)*pow(n/2);
 else return pow(x,n/2)*pow(n/2);
}

@sourcerer · 23.02.2015, 15:31

saden, а так не более читаемо?

C++

double pow(double x, int n)
{
    double result;
    if(n==0)
        result = 1;
    if(n==1)
        result = x;
    if(n&1)
        result = x*pow(x,n/2)*pow(n/2);
    else
        result = pow(x,n/2)*pow(n/2);
 
    return result;
}

ValeryS · 23.02.2015, 15:34

Сообщение от saden

double pow(double x, int n)

как это стыкуется, с этим

Сообщение от gru74ik

pow(n/2)

@saden · 23.02.2015, 15:36

gru74ik, на вкус и цвет... Лишняя переменная в пользу, возможно, читаемости... Тут можно предложить не двойной вызов pow(x,n/2)*pow(n/2), а одинарный через переменную y=pow(x,n/2); return y*y

Добавлено через 45 секунд
ValeryS, ну тарапился... Чего непонятного-то...

@Jewbacabra · 23.02.2015, 15:36

Сообщение от saden

pow(n/2)

А это что такое?

C++

double func(double x, int n) {
    switch (n) {
        case 0: return 1;
        case 1: return x;
        default:
            if (n%2) {
                return x * func(x, n-1);
            } else {
                double tmp = func(x, n/2);
                return tmp * tmp;
            }
    }
}

@saden · 23.02.2015, 15:40

Сообщение от Jewbacabra

return x * func(x, n-1);

А это что такое? Быстрее сразу делить на два

Добавлено через 2 минуты

C++

double pow_rec(double x, int n)
{if(n==0) return 1;
 if(n==1) return x;
 double y = pow_rec(x,n/2);
 if(n&1) return x*y*y;
 return y*y;
}

ValeryS · 23.02.2015, 15:42

вот это лишнее

Сообщение от Jewbacabra

case 1: return x;

попадает в ветку

Сообщение от Fatallol

y = x * y^(n–1)

итого

C++

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

@Fatallol · 23.02.2015, 18:18 **[ТС]**

Спасибо большое, очень помогли. Правда, приятно.

GREGOR_812 · 23.02.2015, 21:08

Сообщение от gru74ik

C++

if(n==1)
    result = x;
if(n&1)
    result = x*pow(x,n/2)*pow(n/2)

В случае с n = 1 этот блок последовательно выполнится

ValeryS Модератор 8908 / 6677 / 918 Регистрация: 14.02.2011 Сообщений: 23,520
	23.02.2015, 15:34	4
	Сообщение от saden double pow(double x, int n) как это стыкуется, с этим Сообщение от gru74ik pow(n/2) 0

@saden 184 / 168 / 53 Регистрация: 27.01.2013 Сообщений: 788
	23.02.2015, 15:36	5
	gru74ik, на вкус и цвет... Лишняя переменная в пользу, возможно, читаемости... Тут можно предложить не двойной вызов pow(x,n/2)pow(n/2), а одинарный через переменную y=pow(x,n/2); return yy Добавлено через 45 секунд ValeryS, ну тарапился... Чего непонятного-то... 0

@Fatallol 0 / 0 / 0 Регистрация: 17.10.2014 Сообщений: 24
	23.02.2015, 18:18 [ТС]	9
	Спасибо большое, очень помогли. Правда, приятно. 0

	23.02.2015, 21:08