Помощь - Поиск - Пользователи - Календарь
Полная версия: Рекурсивная функция [Java]
Форум «Всё о Паскале» > Современный Паскаль и другие языки > Ада и другие языки
Shashlyk
Добрый День!!! Помогите Пожалуйста написать рекурсивную функцию возведения целого числа в целую
неотрицательную степень. Глубина рекурсии не должна превосходить n C 2 log ⋅ , где n – сте­
пень. (Указание: воспользуйтесь алгоритмом «быстрого возведения в степень»).
IUnknown
А ты для начала нерекурсивную функцию напиши, чтоб было понятно, что ты знаешь алгоритм быстрого возведения в целочисленную степень. А уж потом посмотрим, как её преобразовать в рекурсивную...
TarasBer
> А ты для начала нерекурсивную функцию напиши, чтоб было понятно, что ты знаешь алгоритм быстрого возведения в целочисленную степень.

Задание - собрать телегу.
Ты советуешь собрать сначала карету, потом переделать её в телегу.

Я утрирую, но рекурсивный вариант проще, поэтому твой совет выглядит примерно так.
Алгоритм же вот: http://ru.wikipedia.org/wiki/Алгоритм_быст...дения_в_степень
Кода на Java там, правда, нет.
IUnknown
Цитата
Ты советуешь собрать сначала карету, потом переделать её в телегу.
Нет, я советую сначала разобраться, как прилепить к оси колеса, а потом уже начнем собирать что-нибудь, в надежде, что получится именно телега. Хотя рекурсивная функция быстрого возведения в степень не тянет даже на телегу. Это один большой костыль.

Цитата
рекурсивный вариант проще
С каких, интересно, пор рекурсия стала проще для понимания и написания, чем итерация? Обычно сначала разбираются в НЕрекурсивных вещах, а потом - переходят к рекурсии. Особенно с тем уровнем знания/владения инструментом, который ТС показал ранее...
TarasBer
> С каких, интересно, пор рекурсия стала проще для понимания и написания, чем итерация?

Хорошо, напиши обход дерева сначала простыми итерациями, а потом усложни его до рекурсии.

Так вот, быстрое возведение в степень я рекурсией напишу влёт в 3 строчки, без неё - придётся думать, какие переменные заводить, как случаи разбирать, как цикл проходить.
IUnknown
Не надо извращать смысл сказанного мной. Дерево - это рекурсивная структура, да? Вот с ней как раз работать с рекурсией изначально удобнее. А работа с рекурсивной структурой итеративно - это вообще извращение. Возведение числа в степень - это нерекурсивная операция. Поэтому ее изначально проще сделать итеративно.

Цитата
Так вот, быстрое возведение в степень я рекурсией напишу влёт в 3 строчки
На Жабе? Правильно работающую? И с 0 и с 1 и с остальными показателями степени? Удачи.
Shashlyk
Цитата(IUnknown @ 14.09.2011 12:20) *

Не надо извращать смысл сказанного мной. Дерево - это рекурсивная структура, да? Вот с ней как раз работать с рекурсией изначально удобнее. А работа с рекурсивной структурой итеративно - это вообще извращение. Возведение числа в степень - это нерекурсивная операция. Поэтому ее изначально проще сделать итеративно.

На Жабе? Правильно работающую? И с 0 и с 1 и с остальными показателями степени? Удачи.


 static long stepen(int n,int k){
if (k == 0){return 1;} else
{return n * stepen (n , k-1);}
?
IUnknown
Это обычное, а не быстрое возведение в степень с помощью рекурсии. Тебе понадобится ровно n шагов, чтобы возвести число в n-ю степень. Насколько я вижу в первоначальном задании нужно было сделать возведение за меньшее число шагов.
Shashlyk
Цитата(IUnknown @ 14.09.2011 19:10) *

Это обычное, а не быстрое возведение в степень с помощью рекурсии. Тебе понадобится ровно n шагов, чтобы возвести число в n-ю степень. Насколько я вижу в первоначальном задании нужно было сделать возведение за меньшее число шагов.

А как тогда сделать? Помогите Пожалуйста!
IUnknown
Xn =
X * Xn-1, если n - нечетное
Xn/2 * Xn/2, если n - четное
, так и пишем:

public static double f(double base, int ex)
{
if(ex > 0) {
if(ex % 2 == 1) { // Нечетное ?
return base * f(base, ex - 1);
}
else {
double res = f(base, ex / 2);
return res * res;
}
}
else
return 1;
}

Shashlyk
Цитата(IUnknown @ 14.09.2011 19:34) *

Xn =
X * Xn-1, если n - нечетное
Xn/2 * Xn/2, если n - четное
, так и пишем:

public static double f(double base, int ex)
{
if(ex > 0) {
if(ex % 2 == 1) { // Нечетное ?
return base * f(base, ex - 1);
}
else {
double res = f(base, ex / 2);
return res * res;
}
}
else
return 1;
}



Спасибо Вам Большое!!! give_rose.gif
TarasBer
> На Жабе? Правильно работающую? И с 0 и с 1 и с остальными показателями степени? Удачи.

Да

> public static double f(double base, int ex)
> {
> if(ex > 0) {
> if(ex % 2 == 1) { // Нечетное ?
> return base * f(base, ex - 1);
> }
> else {
> double res = f(base, ex / 2);
> return res * res;
> }
> }
> else
> return 1;
> }

Вообще-то ты вот сейчас и написал эти три строчки, только ты их каким-то чудом растянул на 11 (заголовок и внешние фигурные скобки я не считаю), странно, за кол-во строк в кодах на форуме не платят же вроде.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.