LINUX.ORG.RU

Помогите разобраться с рекурсией

 ,


1

1

Добрый день!

Изучаю программирование по учебнику Андрея Столярова. Тема - язык Паскаль и начала программирования. Вопрос касается, в частности, решения задачи 2.12. из задачника того же автора.

"Необходимо построить «ромбик»/«алмаз» из пробелов на фоне, заполненном звездочками. Так, если ввести число 5, программа должна напечатать следующее: "

*******
*** ***
**   **
*     *
**   **
*** ***
*******

Задачу легко решил следующим образом, всё прекрасно работает:

program diamond_cutout;

procedure PrintChars(count: integer);
var
    i: integer;
begin
    for i := 1 to count do
        write('*')
end;

procedure PrintSpaces(count: integer);
var
    i: integer;
begin
    for i := 1 to count do
        write(' ')
end;

procedure PrintLineOfDiamond(i, HH: integer);
begin
    PrintChars(HH + 2 - i);
    PrintSpaces(2 * i - 1);
    PrintChars(HH + 2 - i);
    writeln
end;

procedure PrintFirstLastLineOfDiamond(H: integer);
begin
    PrintChars(H + 2);
    writeln
end;

var
    HalfHeight, i, Height: integer;
begin
    repeat
        write('Enter the diamond''s height (positive, odd)');
        readln(Height);
    until (Height > 0) and (Height mod 2 = 1);
    HalfHeight := Height div 2;
    PrintFirstLastLineOfDiamond(Height);
    for i := 1 to (HalfHeight + 1) do
        PrintLineOfDiamond(i, HalfHeight);
    for i := HalfHeight downto 1 do
        PrintLineOfDiamond(i, HalfHeight);
    PrintFirstLastLineOfDiamond(Height)
end.

Затем, поскольку недавно я прошёл материал по рекурсии, я решил заменить процедуры PrintChars и PrintSpaces на аналогичные, но с использованием рекурсии вместо цикла.

т.е. с

procedure PrintChars(count: integer);
var
    i: integer;
begin
    for i := 1 to count do
        write('*')
end;

на

procedure PrintChars(count: integer);
begin
    if count > 0 then
    begin
        write('*');
        PrintChars(count - 1)
    end
end;

Однако, хотя на выходе (по моему мнению) я должен был получить точно такой же результат как и раньше, я получил

*******
*** ***
** ****
* *****
** ****
*** ***
*******

Это означает, что я что-то неправильно понял в материале по рекурсии. В чём моя ошибка? Почему модифицированный код даёт другой результат?

Почему модифицированный код даёт другой результат?

Похоже PrintSpaces() рекурсивно дёргает за PrintChars(). Но практика на самом деле крайне плоха - не надо никогда заменять итерацию рекурсией, обычно стараются наоборот избавиться от рекурсии в пользу итерации.

bugfixer ★★★★
()
Последнее исправление: bugfixer (всего исправлений: 1)
Ответ на: комментарий от bugfixer

Спасибо за ответ!

Похоже PrintSpaces() рекурсивно дёргает за PrintChars().

Но как такое возможно, если они вынесены в изолированные подпрограммы и одна должна закончиться прежде, чем начнется другая?

KOMMUNIST90
() автор топика
Ответ на: комментарий от bugfixer

Посмотрите на свой PrintSpaces() ещё разок - там явно copy/paste bug.

Можете, пожалуйста, пальцем ткнуть тупому. Не вижу :(((

KOMMUNIST90
() автор топика
Ответ на: комментарий от KOMMUNIST90

Спасибо огромное! :D

Рад помочь :) Главная мысль которую я хотел донести - другая: не увлекайтесь рекурсией. Она применяется на практике очень редко (я, наверное, мог бы ткнуть пальцем всего в пяток мест в нашем codebase этак на 15MLOC). Зачем её господин Столяров упомянул - мне не совсем понятно. Ну, и классический контр-пример - это вычисление N-го числа Фибоначчи. Алгоритмическую стоимость рекурсивного решения предлагаю оценить самостоятельно.

bugfixer ★★★★
()
Последнее исправление: bugfixer (всего исправлений: 1)
Ответ на: комментарий от KOMMUNIST90

Из классиков

Чтобы понять рекурсию, надо сначала понять рекурсию!

hobbit ★★★★★
()
Ответ на: комментарий от bugfixer

не надо никогда заменять итерацию рекурсией

Depends. Помню, ещё в школе в меня намертво вбили это как безусловный императив, с факториалом в качестве примера. А много лет спустя, столкнувшись с ФП, я неожиданно обнаружил, что императив-то оказывается отнюдь не безусловный. Далеко не безусловный.

pr849
()
Ответ на: комментарий от pr849

Depends. Помню, ещё в школе в меня намертво вбили это как безусловный императив, с факториалом в качестве примера.

С факториалом всё не так плохо (особенно если «Tail call optimization» kicks in). С Фибонначи всё гораздо хуже.

А много лет спустя, столкнувшись с ФП, я неожиданно обнаружил, что императив-то оказывается отнюдь не безусловный. Далеко не безусловный.

Я знаю очень мало примеров когда рекурсия что-то упрощает (и никогда если глубина заранее непредсказуема), на моей практике - по пальцам пересчитать.

Кстати - утверждение: любая рекурсия сводится к итерации. Могу доказать.

bugfixer ★★★★
()
Ответ на: комментарий от bugfixer

Я знаю очень мало примеров когда рекурсия что-то упрощает

Я говорил не про упрощение, а про ФП. В котором рекурсия необходима просто в силу иммутабельности: итерация почти всегда требует мутабельных переменных.

Собственно, ИМХО именно поэтому ФП и не любят: приходится переписывать простые итеративные алгоритмы на рекурсивную заумь.

pr849
()
Ответ на: комментарий от bugfixer

Т.е. по существу я с этим согласен:

не надо никогда заменять итерацию рекурсией

Но вот попадёшь в силу обстоятельств в команду повёрнутых ФП-шников – и добро пожаловать в задницу.

pr849
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.