рекурсионная возведение в степень, некак неполучается рекурсией Опции

[maksimla]

Иногда нужна пользоватся экономическим возведением в какуето степень. Чтобы использовать как менше множетелей операций функции надо использовать эти примечание

в скобках написано b четное число
Написать программу которая реализировала экономочный число возведение в степень (с клавиатуры вводим натуральные числа n и m (0 < n ≤ 5, 0 < m ≤ 10), а на экране выводим n число в степени m). Нахождения степени должно быть выражено через рекурсированную функцию.

Я написал программу простую с возведением в степень с процедурой и экономичным или экономическим вариантом но без рекурсии

Program ekokel;
var n,m,a:longint;
 procedure kel(n,m:integer);
 begin
 a:=1;
   while m>0 do
    begin
     a:=a*n;
     dec(m);
     end;
 end;
begin
 writeln('введите число n от 0 до 5');
 readln(n);
 writeln('введите число m от 0 до 10');
 readln(m);
  if m mod 2 = 0 then begin
                       kel(n, m div 2);
                       a:=a*a
                      end
                 else kel(n,m);
  writeln(a);
 readln
end.

а с рекурсированной функцией получается неправильно

Program ekokel;
var n,m,a:longint;
 function kel(n,m:integer):integer;
begin
if m>0 then begin n:=n*n; writeln('n= ',n); kel(n,m div 2); end;
end;
begin
 writeln('введите число n от 0 до 5');
 readln(n);
 writeln('введите число m от 0 до 10');
 readln(m);
  if m mod 2 = 0 then begin
                       kel(n, m div 2);
                       a:=a*a
                      end
                 else kel(n,m);
  writeln(a);
 readln
end.

может подскажете как надо делать

[volvo]

Program ekokel;

function kel(n, m: longint): longint;
begin
  if m = 1 then kel := n
  else
    kel := sqr(n) * kel(n, m - 2);
end;

var n,m,a:longint;

begin
 writeln('введите число n от 0 до 5'); readln(n);
 writeln('введите число m от 0 до 10'); readln(m);

 writeln(kel(n, m));
 { или }
 { a := kel(n, m); writeln(a); }
 readln
end.

[TarasBer]

А что, возводить надо только в нечётную степень?

[maksimla]

если степень четная, то используем этот примечание,если степень нечетное, точда используем простой подсчет

Сообщение отредактировано: maksimla - 7.11.2009 23:08

[volvo]

Нет тут никакого переполнения:

function kel(n, m: longint): longint;
begin
  if m = 0 then kel := 1
  else
    if m = 1 then kel := n
    else
      kel := sqr(n) * kel(n, m - 2);
end;

, проверил со всеми передаваемыми значениями. Если число МОЖЕТ быть вычислено, и помещается в тип LongInt, выдается правильный результат.

[maksimla]

ясно спасибо но я немогу понять этого

 if m = 0 then kel := 1

при воде 2 и 4 то тогда эта будит

kel := 1

но чегото ответ получается правильный непонятно

Сообщение отредактировано: maksimla - 7.11.2009 23:50

[volvo]

но чегото ответ получается правильный непонятно

На то она и рекурсия, чтобы не вычислять ответ сразу, а "собирать" его из кирпичиков, вычисленных на разных этапах.

Смотри: N = 3, M = 4
сразу после вызова: M = 0? Нет... M = 1? Нет... Значит, идем по третьей ветке, рекурсивно вызываем kel(N, M - 2), в нашем случае kel(3, 2)... А потом, когда вернемся сюда - т.е., когда на каком-то витке рекурсии будет M = 0 или M = 1, и рекурсия начнет раскручиваться назад - результат, который она вернет, будет домножен на Sqr(n), то есть на N*N...

Кстати, та моя реализация - не самая эффективная: для того, чтобы вычислить 3¹⁰, надо 6 уровней рекурсии (чтобы проверить - можно сделать так:

function kel(n, m: longint): longint;
begin
  writeln('*');
  if m = 0 then kel := 1
  else
    if m = 1 then kel := n
    else
      kel := sqr(n) * kel(n, m - 2);
end;

, и посчитать, сколько звездочек будет напечатано, каждая звездочка - новый уровень рекурсии).

Вот такое решение:

function kel(n, m: longint): longint;
begin
  writeln('*');
  if (n = 0) or (m = 0) then kel := 1
  else
    if m = 1 then kel := n
    else
      kel := sqr(kel(n, m div 2)) * succ((m mod 2)*pred(n));
end;

для вычисления 3¹⁰ "забирается" всего на 4-ый уровень, то есть, более эффективно работает.