Базовый и рекурсивный случаи

Алла: А куда мы идём?

Тимофей: На встречу с Кондратием. У него, как всегда, какая-то важная проблема, и он сказал всем программистам приехать к нему на виллу в Удотинск.

Рита: А долго ещё?

Тимофей: Часа два примерно.

Гоша: Это же целых 120 минут! Кстати, Тимофей, потренировался я писать твои эти рекурсивные программы, но что-то вечно комп зависал.

Тимофей: Запуск бесконечного цикла — пожалуй, самая частая ошибка при написании рекурсивных программ!

Гоша: Чего?

Тимофей: Помнишь, мы писали программу, которая создаёт матрёшек? Мы использовали условие:

Скопировать кодPYTHON
if n >= 1:

Тимофей: Как вы думаете, для чего?

Алла: Чтобы внутри не было нулевых и отрицательных матрёшек?

Тимофей: Если этого не сделать, функция не завершит свою работу. Предположим, вы пишите функцию timer, которая реализует алгоритм обратного отсчёта минут и определяет, сколько нам осталось идти.

Кажется, код такой функции, реализованной с применением рекурсии на Python, может выглядеть так:

Скопировать кодPYTHON
import time

def timer(n):
    time.sleep(60)
    print("Осталось идти {} минут".format(n))
    timer(n - 1)

На самом деле, мы получили бесконечный цикл. После n=0 функция вызовется со значением -1, потом с -2 и так далее.

При написании рекурсивной функции нужно указывать краевой случай. То есть условие, при котором нужно выйти из рекурсии. А также определить, что должно происходить в базовом случае.

Алла: Так в базовом или краевом?

Тимофей: Это одно и то же. Базовый случай иногда называют краевым.

Например, в функции timer можно сделать обратный отсчёт до нуля:

Скопировать кодPYTHON
def timer(n):
    if n < 0:
        return
    time.sleep(60)
    print("Осталось идти {} минут".format(n))
    timer(n - 1)

Прежде, чем писать рекурсивную функцию, нужно решить:

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

Программирование рекурсивной функции выглядит так:

Проверяем, является ли переданный набор параметров базовым случаем. Если да, то функция должна вернуть значение либо выполнить действия, заданные для базового случая.
Иначе функция должна вызвать себя рекурсивно с другими значениями параметров. На основе полученных знаний вычисляем результат, который она должна вернуть.

Гоша: А, теперь понятно.

Тимофей: Проверим, насколько понятно. Допустим, мы хотим рекурсивно посчитать сумму элементов в массиве. Это не самый удобный способ нахождения суммы, но будет полезно проделать это упражнение для закрепления материала.

Пусть на вход подан массив arr = [1, 2, 3, 4, 5].

Какой тут базовый случай?

Гоша: Рекурсию нужно прервать, когда длина массива равна 1.

Скопировать кодPYTHON
def _findSum(arr): 
     if len(arr) == 1: 
        return arr[0] 
     else: 
        return arr[0] + _findSum(arr[1:])

Посмотрим, что происходит при вызове функции _findSum для массива arr = [1, 2, 3, 4, 5].

При первом вызове в функцию передается весь массив. Итог вычисления — сумма первого элемента, то есть 1, и результата вызова функции для массива [2, 3, 4, 5].

Чтобы вычислить значение функции для массива [2, 3, 4, 5], нужно к 2 прибавить результат функции для [3, 4, 5].

И так далее, пока не дойдём до массива [5]. Когда это произойдёт, нужно вернуть элемент массива на позиции 0, то есть 5.

Массив из одного элемента — базовый случай для данной задачи. Если его не указать, произойдет вызов функции с пустым массивом. Это приведёт к обращению по несуществующему индексу.

Гоша: Ну вот, я же говорил, что именно такой базовый случай!

Какой будет базовый случай, если вычислять сумму чисел от 0 до n?

n = 0

В этой задаче в качестве базового случая можно выбрать n = 1.

Скопировать кодPYTHON
def sum(n):
    if n == 1:
        return 1
    else:
        return n + sum(n — 1)

А можно выбрать n = 0.

Скопировать кодPYTHON
def sum(n):
    if n == 0:
        return 0
    else:
        return n + sum(n — 1)

n = 1

В этой задаче в качестве базового случая можно выбрать n = 1.

Скопировать кодPYTHON
def sum(n):
    if n == 1:
        return 1
    else:
        return n + sum(n — 1)

А можно выбрать n = 0.

Скопировать кодPYTHON
def sum(n):
    if n == 0:
        return 0
    else:
        return n + sum(n — 1)

n = 2

В этой задаче в качестве базового случая можно выбрать n = 1.

Скопировать кодPYTHON
def sum(n):
    if n == 1:
        return 1
    else:
        return n + sum(n — 1)

А можно выбрать n = 0.

Скопировать кодPYTHON
def sum(n):
    if n == 0:
        return 0
    else:
        return n + sum(n — 1)

2 из 3 правильно и 1 неправильно

Гоша: Правда, при выборе n = 0 в качестве базового случая, мы лишний раз прибавим ноль

Есть ли недостатки в выборе n = 1 базовым случаем алгоритма?

Один недостаток — придётся прибавить ноль.

При вызове функции с n = 0 получим бесконечный цикл.

Функция не будет работать.

Можно получить бесконечный цикл.

Недостатков нет.

Время решить задачи E и F: https://contest.yandex.ru/contest/18359/problems/E/ .