Рекурсивные решения двух простых задач

Задача #1

Найти сумму всех чисел в диапазоне [A, B], AB.

Решения

Как рекурсивно найти сумму в диапазоне [A, B]?

Sum(A, B) = A + Sum(A + 1, B)
Sum(B, B) = B

Запрограммируем это очевидное решение.

function SumInRangeDraft(a, b: integer): integer;
begin
  if a = b then
    Result := a
  else
    Result := a + SumInRangeDraft(a + 1, b);
end;

Отлично! Проверим…

Writeln(SumInRangeDraft(3, 6));  >>> 18
Writeln
(SumInRangeDraft(1, 4)); >>> 10
Writeln
(SumInRangeDraft(-3, 1)); >>> -5
Writeln
(SumInRangeDraft(7, 7)); >>> 7

А теперь так:

Writeln(SumInRangeDraft(6,1));

Ой!
Ошибка — переполнение программного стека.

Разберёмся, что произошло. Можно запустить отладчик или выполнить программу «руками».

SumInRangeDraft(6, 1)

    [6 <> 1: ветка else]
    6 + SumInRangeDraft(7 [6 + 1], 1)
    
        [7 <> 1: ветка else]
        7 + SumInRangeDraft(8 [7 + 1], 1)
        
            [8 <> 1: ветка else]
            8 + SumInRangeDraft(9, 1)
            
...

Причина понятна: мы зациклились при изначальном соотношении параметров a > b.
Рекурсивные вызовы никогда не заканчиваются, первый параметр a всё дальше удаляется от b.

Что делать?

Решение 1-1 (нестрогое)

В диапазоне [A, B], A > B никаких чисел нет, поэтому их сумма равна 0.

function SumInRangeBad1(a, b: integer): integer;
begin
  if a > b then
    Result := 0
  else if a = b then
    Result := a
  else
    Result := a + SumInRangeBad1(a + 1, b);
end;

Замечание. Иначе можно написать и так:

function SumInRangeBad1(a, b: integer): integer;
begin
  if a > b then
  begin
    Result := 0;
    exit;
  end;
  if a = b then
    Result := a
  else
    Result := a + SumInRangeBad1(a + 1, b);
end;

И ещё так:

function SumInRangeBad1(a, b: integer): integer;
begin
  if a > b then
  begin
    Result := 0;
    exit;
  end;
  Result := a;
  if a < b then
    Result += SumInRangeBad1(a + 1, b);
end;

Решение 1-2 (нестрогое)

Какая разница, от A до B или от B до A? Диапазон — он и в Африке диапазон. Давайте просто поменяем A и B местами.

function SumInRangeBad2(a, b: integer): integer;
begin
  if a > b then
    Swap(a, b);
  if a = b then
    Result := a
  else
    Result := a + SumInRangeBad2(a + 1, b);
end;

Какое решение лучше?

Правильный ответ — никакое. Формулировка задачи такова: «Найти сумму всех чисел в диапазоне [A, B], AB». В условии ничего не сказано о случае, когда A > B.
Оба решения в принципе имеют право на существование. Но поскольку в данной задаче условие не даёт никаких специальных указаний на этот счёт, нет никаких оснований предпочесть одно решение другому.

Наша функция должна правильно решать поставленную задачу в заданной области определения (AB) и не должна делать ничего лишнего.
Один из вариантов обезопасить себя от неправильных входных данных — проверить это с помощью Assert. Таким образом мы отказываемся работать с неправильными входными данными, и ответственность за правильное использование нашей функции полностью лежит на вызывающей стороне.

Большая красная кнопка. Доступ к ядерному чемоданчику есть только у президента страны. Функция «обработать нажатие большой красной кнопки для запуска ракеты» должна работать только для одного значения входных данных — отпечатков пальцев президента (или сетчатки глаза, или ещё более продвинутого способа биоидентификации). В остальных случаях она вообще не должна работать.
Если программист вместо того, чтобы поставить Assert и отказаться работать с неправильными входными данными, принял какое-то неявное решение (например, по умолчанию отправлять ракету в Антарктиду) — это, очевидно, может обернуться серьёзными негативными последствиями.

То же самое и для наших подпрограмм. Если область определения входных данных чётко задана, подпрограмма должна работать с этими входными данными и не должна работать ни с какими другими.

Решение 2 (строгое)

Добавим в нашу подпрограмму проверку входных данных.

function SumInRangeGood1(a, b: integer): integer;
begin
Assert(a <= b, 'SumInRangeGood1: a <= b');
if a = b then
Result := a
else
Result := a + SumInRangeGood1(a + 1, b);
end;

Решение #3 (строгое)

Присмотримся к решению. Видно, что обе ветки содержат одинаковый код:

function SumInRangeGood1(a, b: integer): integer;
begin
Assert(a <= b, 'SumInRangeGood1: a <= b');
if a = b then
Result := a
else
Result := a + SumInRangeGood1(a + 1, b);
end;

Если один и тот же код выполняется по всем веткам, его можно вынести из условного оператора. Получим следующее решение:

function SumInRangeGood2(a, b: integer): integer;
begin
Assert(a <= b, 'SumInRangeGood2: a <= b');
Result := a;
if a < b then
Result += SumInRangeGood2(a + 1, b);
end;

Как мы получили условие в if?
Рекурсивный вызов происходил по ветке else для условия a = b. То есть по условию ab.
Но допустимые входные данные — это случай ab. Выбрасываем из него случай a = b и получаем a < b.

Решения 4-5 (строгие)

Заметим, что сумма чисел в диапазоне [A, B] это также и:

Sum(A, B) = Sum(A, B - 1) + B
Sum(A, A) = A

Поэтому с таким же успехом по диапазону входных данных мы можем двигаться и сверху вниз:

function SumInRangeGood3(a, b: integer): integer;
begin
Assert(a <= b, 'SumInRangeGood3: a <= b');
if b = a then
Result := b
else
Result := b + SumInRangeGood3(a, b - 1);
end;
function SumInRangeGood4(a, b: integer): integer;
begin
Assert(a <= b, 'SumInRangeGood4: a <= b');
Result := b;
if b > a then
Result += SumInRangeGood4(a, b - 1);
end;

Задача #2

Найти сумму всех нечётных чисел в диапазоне [A, B], AB.

Решения

Задача очень похожа, но добавилось условие на числа, которые необходимо учитывать в сумме. Для начала попробуем расписать рекурсивное определение, как и в прошлой задаче.

Sum(A, B) | A — нечётное = A + Sum(A + 1, B)
Sum(A, B) | A — чётное   = Sum(A + 1, B)

Пока понятно. А где базовый случай?

Sum(B, B) | B — нечётное = B
Sum(B, B) | B — чётное   = 0

Уже видно, что определение не очень хорошее: нам всегда приходится проверять чётность числа. Ну, ладно, давайте запрограммируем.

function OddSumInRangeGood1(a, b: integer): integer;
begin
Assert(a <= b, 'OddSumInRangeGood1: a <= b');
if a = b then
if Odd(a) then
Result := a
else
Result := 0
else
if Odd(a) then
Result := a + OddSumInRangeGood1(a + 1, b)
else
Result := OddSumInRangeGood1(a + 1, b);
end;

Решение верное, но не слишком элегантное. Куча дублирующегося кода.

function OddSumInRangeGood1(a, b: integer): integer;
begin
Assert(a <= b, 'OddSumInRangeGood1: a <= b');
if a = b then
if Odd(a) then
Result := a
else
Result := 0
else
if Odd(a) then
Result := a + OddSumInRangeGood1(a + 1, b)
else
Result := 0 + OddSumInRangeGood1(a + 1, b);
end;

Вынесем оранжевую дублирующую часть за пределы условного оператора. Голубая часть «схлопнется» автоматически (так как мы уберём из внешней ветки else внутренний условный оператор).

function OddSumInRangeGood2(a, b: integer): integer;
begin
Assert(a <= b, 'OddSumInRangeGood2: a <= b');
if Odd(a) then
Result := a
else
Result := 0;
if a < b then
Result += OddSumInRangeGood2(a + 1, b);
end;

Другой подход

Если немного подумать над рекурсивным определением и убрать дублирующуюся часть уже из него, мы получим вот такое определение:

Sum(A, B) | A — нечётное = A + Sum(A + 1, B)
Sum(A, B) | A — чётное = Sum(A + 1, B)

Sum(B + 1, B) = 0

В качестве простейшего случая мы просто выбрали пустой диапазон, а не диапазон из одного элемента. Это решение легко запрограммировать:

function OddSumInRangeDraft1(a, b: integer): integer;
begin
if a = b + 1 then
Result := 0
else if Odd(a) then
Result := a + OddSumInRangeDraft1(a + 1, b);
else
Result := OddSumInRangeDraft1(a + 1, b);
end;

Чтобы не дублировать код рекурсивного вызова можно сделать так:

function OddSumInRangeDraft2(a, b: integer): integer;
begin
if a = b + 1 then
begin
Result := 0;
exit;
end;
if Odd(a) then
Result := a;
else
Result := 0;
Result += OddSumInRangeDraft2(a + 1, b);
end;

Но что же тогда делать с проверкой входных данных? Мы ведь только что говорили про большую красную кнопку, а тут вдруг в решении появилось недопустимое условие a = b + 1. Нет, пользователю нельзя позволять такое. Но это условие нужно нам для решения задачи!

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

function OddSumInRangeGood3(a, b: integer): integer;

function OddSumInRangeNested(a, b: integer): integer;
begin
Assert(a <= b + 1, 'OddSumInRangeNested: a <= b + 1');
if a = b + 1 then
Result := 0
else
begin
if Odd(a) then
Result := a
else
Result := 0;
Result += OddSumInRangeNested(a + 1, b);
end;
end;

begin
Assert(a <= b, 'OddSumInRangeGood3: a <= b');
Result := OddSumInRangeNested(a, b);
end;

Замечание. Обратите внимание, что решение #3 в некотором смысле лучше решения #1, где был дублирующися код. А решение #2 выглядит лучше, чем решение #3, хотя воспринимать его может быть труднее. Одна задача может иметь много вариантов решения, это нормально.

Последнее изменение: Monday, 18 April 2016, 17:03