Рекурсивная функция [Java] Опции

[Shashlyk]

Добрый День!!! Помогите Пожалуйста написать рекурсивную функцию возведения целого числа в целую
неотрицательную степень. Глубина рекурсии не должна превосходить n C 2 log ⋅ , где n – сте­
пень. (Указание: воспользуйтесь алгоритмом «быстрого возведения в степень»).

[IUnknown]

А ты для начала нерекурсивную функцию напиши, чтоб было понятно, что ты знаешь алгоритм быстрого возведения в целочисленную степень. А уж потом посмотрим, как её преобразовать в рекурсивную...

[TarasBer]

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

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

Я утрирую, но рекурсивный вариант проще, поэтому твой совет выглядит примерно так.
Алгоритм же вот: http://ru.wikipedia.org/wiki/Алгоритм_быст...дения_в_степень
Кода на Java там, правда, нет.

[IUnknown]

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

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

рекурсивный вариант проще

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

Сообщение отредактировано: IUnknown - 14.09.2011 11:09

[TarasBer]

> С каких, интересно, пор рекурсия стала проще для понимания и написания, чем итерация?

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

Так вот, быстрое возведение в степень я рекурсией напишу влёт в 3 строчки, без неё - придётся думать, какие переменные заводить, как случаи разбирать, как цикл проходить.

[IUnknown]

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

Так вот, быстрое возведение в степень я рекурсией напишу влёт в 3 строчки

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

[Shashlyk]

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

На Жабе? Правильно работающую? И с 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]

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

А как тогда сделать? Помогите Пожалуйста!

[IUnknown]

Xⁿ =
X * X^n-1, если n - нечетное
X^n/2 * X^n/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]

Xⁿ =
X * X^n-1, если n - нечетное
X^n/2 * X^n/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;
}

Спасибо Вам Большое!!!

[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 (заголовок и внешние фигурные скобки я не считаю), странно, за кол-во строк в кодах на форуме не платят же вроде.