На этом шаге мы рассмотрим несколько рекурсивных программ.

Для использования рекурсии при разработке алгоритмов крайне важно знать, как разбить задачу на меньшие себе подобные и определить рекурсивные методы, опираясь на индукцию. Как только это сделано, дальше уже не составит труда преобразовать определения в код, особенно для таких базовых типов данных, как целые и вещественные числа, символы или логические (булевы) значения. Рассмотрим функцию (1.5), которая суммирует первые n целых положительных (натуральных) чисел. В языке Python такая функция может быть закодирована, как показано в примере 1.1. Аналогия между (1.5) и функцией Python очевидна.

Пример 1.1. Суммирование первых n натуральных чисел

1
2
3
4
5

def sum_first_naturals(n):
    if n == 1:
        return 1 # Base case
    else:
         return sum_first_naturals(n - 1) + n # Recursive case

Архив с файлом можно взять здесь.

Как и во многих следующих примерах, обычный условный оператор - единственная управляющая конструкция, необходимая для реализации рекурсивной функции.

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

Код функции в других языках программирования так же прост. Ниже показаны эквивалентные коды на нескольких языках программирования.

C, Java:

1
2
3
4
5
6
7

int sum_first_naturals(int n)
{
  if (n == 1)
    return 1;
 else:
   return sum first naturals(n-l) + n;  
}

Pascal:

1
2
3
4
5
6
7

function sum_first_naturals(n: integer): integer;
begin
  if n=1 then
    sum_first_naturals := 1
  else
  sum_first_naturals := sum_first_naturals(n-1) + n;  
end;

MATLAB:

1
2
3
4
5
6

function result = sum_first_naturals(n)
  if n==1
    result = 1;
  else
    result = sum_first_naturals(n-1) + n;  
end

Scala:

1
2
3
4
5
6

def sum_first_naturals(n: Int): Int = {  
  if (n==1)
    return 1
  else
    return sum first naturals(n-l) + n
}

Haskell:

1 2	sum_first_naturals 1 = 1 sum_first_naturals n = sum_first_naturals (n - 1) + n

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

Важно, что в функции (1.5) и в соответствующем ей коде не проверяется условие n > 0. Для входного параметра такой тип условия, задаваемого в постановке задачи или в определении функции, известен как предусловие. Программисты могут считать, что предусловия соблюдаются всегда и потому не должны создавать код для их поиска или обработки.

Пример 1.2 соответствует рекурсивному определению (1.6).

Пример 1.2. Другой вариант суммирования первых n натуральных чисел

1
2
3
4
5
6
7
8
9
10
11

def sum_first_naturals(n):
    if n == 1:
        return 1
    elif n == 2:
        return 3
    elif n % 2 != 0:
        return 3 * sum_first_naturals((n - 1) // 2) + \  
               sum_first_naturals((n + 1) / 2)
    else:
        return 3 * sum_first_naturals(n // 2) + \
               sum_first_naturals(n // 2 - 1)

Архив с файлом можно взять здесь.

Рекурсивная функция использует каскадный условный оператор для выбора одного из двух начальных (строки 2-5) и рекурсивных условий (строки 6-11), где два последних дважды вызывают саму рекурсивную функцию.

Так же просто закодировать функцию, вычисляющую n-е число Фибоначчи согласно стандартному определению (1.2). В примере 1.3 приводится соответствующий код, где оба начальных условия проверяются в логическом выражении условного оператора.

Пример 1.3. Вычисление n-го числа Фибоначчи

1
2
3
4
5

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

Архив с файлом можно взять здесь.

Реализация функции Фибоначчи (1.7) требует большего количества действий. Если начальные условия идентичны, суммирование в рекурсивном условии нуждается в операторе цикла или иной функции для вычисления суммы значений F(1), F(2), ..., F(n - 2). В примере 1.4 приводится возможное решение с использованием цикла for.

Пример 1.4. Другой вариант вычисления n-го числа Фибоначчи

1
2
3
4
5
6
7
8

def fibonacci_alt(n):
    if n == 1 or n == 2:
        return 1
    else:
        aux = 1
        for i in range(1, n - 1):
            aux += fibonacci_alt(i)  
        return aux

Архив с файлом можно взять здесь.

Результат сложения можно сохранить во вспомогательной переменной-сумматоре aux с начальным значением 1 (строка 5). Цикл for просто добавляет к вспомогательной переменной члены F(i) для i = 1, ..., n - 2 (строки 6-7). В итоге функция возвращает вычисленное и сохранённое в aux число Фибоначчи.

На следующем шаге мы закончим изучение этого вопроса.

Предыдущий шаг Содержание Следующий шаг