Знакомство с рекурсией — различия между версиями

Текущая версия на 22:34, 19 апреля 2016

Для решения задачи с помощью рекурсии в этой задаче нужно увидеть две вещи:

1. Возможность обработки некоторой подзадачи.

1. Подзадача должна иметь такой вид: это исходная задача, но в меньшем объёме.

Примеры

Задача #1. Разнести почту в заданные дома района.
Решение.

1. Разложить почту в почтовые ящики некоторого дома.
2. Разнести почту в оставшиеся дома района.

Задача #2. Дан линейный односвязный список персиков. Собрать все персики из списка в корзину.
Решение.

1. Взять персики из головы списка и положить их в корзину.
2. Собрать в ту же корзину все персики из оставшейся части (хвоста) списка.

Задача #3. Есть 100 мешков картошки, которую нужно почистить. Автомат-картофелечистка за один «присест» умеет чистить только один мешок.
Решение.

1. Загрузить в автомат один мешок картошки, почистить.
2. Почистить 99 мешков картошки.

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

Примеры.

1. Базовый случай для задачи #1: не осталось домов, в которые нужно разносить почту. Это значит, что работа почтальона закончена, алгоритм завершается.
2. Базовый случай для задачи #2: список с персиками закончился, собирать больше нечего. Радостно берём корзину с собранными персиками и идём, куда нам нужно.

Замечание. Без обработки базового случая произойдёт зацикливание.

Метод вложенной функции

    function SumPositive(a, b: integer): integer;
    
      function SumPositiveNested(a, b: integer): integer;
      begin
        // здесь a может быть равно b
        if a > 0 then
          Result := a
        else
          Result := 0;
        if a < b then
          Result += SumPositiveNested(a + 1, b);
      end;
    
    begin
      Assert(a < b);
      Result := SumPositiveNested(a, b);
    end;