Перейти к содержанию

2.2   Итерация и рекурсия

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

2.2.1   Итерация

Итерация (iteration) - это структура управления, которая позволяет повторно выполнять определенную задачу. В итерации программа повторяет выполнение определенного участка кода, пока выполняется определенное условие.

1.   Цикл for

Цикл for - одна из наиболее распространенных форм итерации, которая подходит для использования, когда количество итераций известно заранее.

Следующая функция реализует суммирование \(1 + 2 + \dots + n\) с использованием цикла for , а результат суммирования сохраняется в переменной res . Следует отметить, что в Python диапазон range(a, b) соответствует левому закрытому, правому открытому интервалу, то есть перебираются значения \(a, a + 1, \dots, b-1\) :

iteration.py
def for_loop(n: int) -> int:
    """Цикл for"""
    res = 0
    # Циклическое суммирование 1, 2, ..., n-1, n
    for i in range(1, n + 1):
        res += i
    return res
iteration.cpp
/* Цикл for */
int forLoop(int n) {
    int res = 0;
    // Циклическое суммирование 1, 2, ..., n-1, n
    for (int i = 1; i <= n; ++i) {
        res += i;
    }
    return res;
}
iteration.java
/* Цикл for */
int forLoop(int n) {
    int res = 0;
    // Циклическое суммирование 1, 2, ..., n-1, n
    for (int i = 1; i <= n; i++) {
        res += i;
    }
    return res;
}
iteration.cs
/* Цикл for */
int ForLoop(int n) {
    int res = 0;
    // Циклическое суммирование 1, 2, ..., n-1, n
    for (int i = 1; i <= n; i++) {
        res += i;
    }
    return res;
}
iteration.go
/* Цикл for */
func forLoop(n int) int {
    res := 0
    // Циклическое суммирование 1, 2, ..., n-1, n
    for i := 1; i <= n; i++ {
        res += i
    }
    return res
}
iteration.swift
/* Цикл for */
func forLoop(n: Int) -> Int {
    var res = 0
    // Циклическое суммирование 1, 2, ..., n-1, n
    for i in 1 ... n {
        res += i
    }
    return res
}
iteration.js
/* Цикл for */
function forLoop(n) {
    let res = 0;
    // Циклическое суммирование 1, 2, ..., n-1, n
    for (let i = 1; i <= n; i++) {
        res += i;
    }
    return res;
}
iteration.ts
/* Цикл for */
function forLoop(n: number): number {
    let res = 0;
    // Циклическое суммирование 1, 2, ..., n-1, n
    for (let i = 1; i <= n; i++) {
        res += i;
    }
    return res;
}
iteration.dart
/* Цикл for */
int forLoop(int n) {
  int res = 0;
  // Циклическое суммирование 1, 2, ..., n-1, n
  for (int i = 1; i <= n; i++) {
    res += i;
  }
  return res;
}
iteration.rs
/* Цикл for */
fn for_loop(n: i32) -> i32 {
    let mut res = 0;
    // Циклическое суммирование 1, 2, ..., n-1, n
    for i in 1..=n {
        res += i;
    }
    res
}
iteration.c
/* Цикл for */
int forLoop(int n) {
    int res = 0;
    // Циклическое суммирование 1, 2, ..., n-1, n
    for (int i = 1; i <= n; i++) {
        res += i;
    }
    return res;
}
iteration.kt
/* Цикл for */
fun forLoop(n: Int): Int {
    var res = 0
    // Циклическое суммирование 1, 2, ..., n-1, n
    for (i in 1..n) {
        res += i
    }
    return res
}
iteration.rb
### Цикл for ###
def for_loop(n)
  res = 0

  # Циклическое суммирование 1, 2, ..., n-1, n
  for i in 1..n
    res += i
  end

  res
end
Визуализация кода

На рисунке 2-1 представлена блок-схема этой функции суммирования.

Блок-схема функции суммирования

Рисунок 2-1   Блок-схема функции суммирования

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

2.   Цикл while

Подобно циклу for , цикл while также представляет собой метод реализации итерации. В цикле while программа перед каждой итерацией проверяет условие: если условие истинно, то выполнение продолжается, иначе цикл завершается.

Ниже приведен пример реализации суммирования \(1 + 2 + \dots + n\) с использованием цикла while :

iteration.py
def while_loop(n: int) -> int:
    """Цикл while"""
    res = 0
    i = 1  # Инициализация условной переменной
    # Циклическое суммирование 1, 2, ..., n-1, n
    while i <= n:
        res += i
        i += 1  # Обновить условную переменную
    return res
iteration.cpp
/* Цикл while */
int whileLoop(int n) {
    int res = 0;
    int i = 1; // Инициализация условной переменной
    // Циклическое суммирование 1, 2, ..., n-1, n
    while (i <= n) {
        res += i;
        i++; // Обновить условную переменную
    }
    return res;
}
iteration.java
/* Цикл while */
int whileLoop(int n) {
    int res = 0;
    int i = 1; // Инициализация условной переменной
    // Циклическое суммирование 1, 2, ..., n-1, n
    while (i <= n) {
        res += i;
        i++; // Обновить условную переменную
    }
    return res;
}
iteration.cs
/* Цикл while */
int WhileLoop(int n) {
    int res = 0;
    int i = 1; // Инициализация условной переменной
    // Циклическое суммирование 1, 2, ..., n-1, n
    while (i <= n) {
        res += i;
        i += 1; // Обновить условную переменную
    }
    return res;
}
iteration.go
/* Цикл while */
func whileLoop(n int) int {
    res := 0
    // Инициализация условной переменной
    i := 1
    // Циклическое суммирование 1, 2, ..., n-1, n
    for i <= n {
        res += i
        // Обновить условную переменную
        i++
    }
    return res
}
iteration.swift
/* Цикл while */
func whileLoop(n: Int) -> Int {
    var res = 0
    var i = 1 // Инициализация условной переменной
    // Циклическое суммирование 1, 2, ..., n-1, n
    while i <= n {
        res += i
        i += 1 // Обновить условную переменную
    }
    return res
}
iteration.js
/* Цикл while */
function whileLoop(n) {
    let res = 0;
    let i = 1; // Инициализация условной переменной
    // Циклическое суммирование 1, 2, ..., n-1, n
    while (i <= n) {
        res += i;
        i++; // Обновить условную переменную
    }
    return res;
}
iteration.ts
/* Цикл while */
function whileLoop(n: number): number {
    let res = 0;
    let i = 1; // Инициализация условной переменной
    // Циклическое суммирование 1, 2, ..., n-1, n
    while (i <= n) {
        res += i;
        i++; // Обновить условную переменную
    }
    return res;
}
iteration.dart
/* Цикл while */
int whileLoop(int n) {
  int res = 0;
  int i = 1; // Инициализация условной переменной
  // Циклическое суммирование 1, 2, ..., n-1, n
  while (i <= n) {
    res += i;
    i++; // Обновить условную переменную
  }
  return res;
}
iteration.rs
/* Цикл while */
fn while_loop(n: i32) -> i32 {
    let mut res = 0;
    let mut i = 1; // Инициализация условной переменной

    // Циклическое суммирование 1, 2, ..., n-1, n
    while i <= n {
        res += i;
        i += 1; // Обновить условную переменную
    }
    res
}
iteration.c
/* Цикл while */
int whileLoop(int n) {
    int res = 0;
    int i = 1; // Инициализация условной переменной
    // Циклическое суммирование 1, 2, ..., n-1, n
    while (i <= n) {
        res += i;
        i++; // Обновить условную переменную
    }
    return res;
}
iteration.kt
/* Цикл while */
fun whileLoop(n: Int): Int {
    var res = 0
    var i = 1 // Инициализация условной переменной
    // Циклическое суммирование 1, 2, ..., n-1, n
    while (i <= n) {
        res += i
        i++ // Обновить условную переменную
    }
    return res
}
iteration.rb
### Цикл while ###
def while_loop(n)
  res = 0
  i = 1 # Инициализация условной переменной

  # Циклическое суммирование 1, 2, ..., n-1, n
  while i <= n
    res += i
    i += 1 # Обновить условную переменную
  end

  res
end
Визуализация кода

**Цикл while обладает большей степенью свободы по сравнению с циклом for **. В цикле while можно свободно управлять инициализацией и обновлением условной переменной.

Например, в следующем коде условная переменная \(i\) обновляется дважды на каждой итерации, что затруднительно сделать с использованием цикла for :

iteration.py
def while_loop_ii(n: int) -> int:
    """Цикл while (двойное обновление)"""
    res = 0
    i = 1  # Инициализация условной переменной
    # Циклическое суммирование 1, 4, 10, ...
    while i <= n:
        res += i
        # Обновить условную переменную
        i += 1
        i *= 2
    return res
iteration.cpp
/* Цикл while (двойное обновление) */
int whileLoopII(int n) {
    int res = 0;
    int i = 1; // Инициализация условной переменной
    // Циклическое суммирование 1, 4, 10, ...
    while (i <= n) {
        res += i;
        // Обновить условную переменную
        i++;
        i *= 2;
    }
    return res;
}
iteration.java
/* Цикл while (двойное обновление) */
int whileLoopII(int n) {
    int res = 0;
    int i = 1; // Инициализация условной переменной
    // Циклическое суммирование 1, 4, 10, ...
    while (i <= n) {
        res += i;
        // Обновить условную переменную
        i++;
        i *= 2;
    }
    return res;
}
iteration.cs
/* Цикл while (двойное обновление) */
int WhileLoopII(int n) {
    int res = 0;
    int i = 1; // Инициализация условной переменной
    // Циклическое суммирование 1, 4, 10, ...
    while (i <= n) {
        res += i;
        // Обновить условную переменную
        i += 1; 
        i *= 2;
    }
    return res;
}
iteration.go
/* Цикл while (двойное обновление) */
func whileLoopII(n int) int {
    res := 0
    // Инициализация условной переменной
    i := 1
    // Циклическое суммирование 1, 4, 10, ...
    for i <= n {
        res += i
        // Обновить условную переменную
        i++
        i *= 2
    }
    return res
}
iteration.swift
/* Цикл while (двойное обновление) */
func whileLoopII(n: Int) -> Int {
    var res = 0
    var i = 1 // Инициализация условной переменной
    // Циклическое суммирование 1, 4, 10, ...
    while i <= n {
        res += i
        // Обновить условную переменную
        i += 1
        i *= 2
    }
    return res
}
iteration.js
/* Цикл while (двойное обновление) */
function whileLoopII(n) {
    let res = 0;
    let i = 1; // Инициализация условной переменной
    // Циклическое суммирование 1, 4, 10, ...
    while (i <= n) {
        res += i;
        // Обновить условную переменную
        i++;
        i *= 2;
    }
    return res;
}
iteration.ts
/* Цикл while (двойное обновление) */
function whileLoopII(n: number): number {
    let res = 0;
    let i = 1; // Инициализация условной переменной
    // Циклическое суммирование 1, 4, 10, ...
    while (i <= n) {
        res += i;
        // Обновить условную переменную
        i++;
        i *= 2;
    }
    return res;
}
iteration.dart
/* Цикл while (двойное обновление) */
int whileLoopII(int n) {
  int res = 0;
  int i = 1; // Инициализация условной переменной
  // Циклическое суммирование 1, 4, 10, ...
  while (i <= n) {
    res += i;
    // Обновить условную переменную
    i++;
    i *= 2;
  }
  return res;
}
iteration.rs
/* Цикл while (двойное обновление) */
fn while_loop_ii(n: i32) -> i32 {
    let mut res = 0;
    let mut i = 1; // Инициализация условной переменной

    // Циклическое суммирование 1, 4, 10, ...
    while i <= n {
        res += i;
        // Обновить условную переменную
        i += 1;
        i *= 2;
    }
    res
}
iteration.c
/* Цикл while (двойное обновление) */
int whileLoopII(int n) {
    int res = 0;
    int i = 1; // Инициализация условной переменной
    // Циклическое суммирование 1, 4, 10, ...
    while (i <= n) {
        res += i;
        // Обновить условную переменную
        i++;
        i *= 2;
    }
    return res;
}
iteration.kt
/* Цикл while (двойное обновление) */
fun whileLoopII(n: Int): Int {
    var res = 0
    var i = 1 // Инициализация условной переменной
    // Циклическое суммирование 1, 4, 10, ...
    while (i <= n) {
        res += i
        // Обновить условную переменную
        i++
        i *= 2
    }
    return res
}
iteration.rb
### Цикл while ###
def while_loop(n)
  res = 0
  i = 1 # Инициализация условной переменной

  # Циклическое суммирование 1, 2, ..., n-1, n
  while i <= n
    res += i
    i += 1 # Обновить условную переменную
  end

  res
end

# ## Цикл while (двойное обновление) ###
def while_loop_ii(n)
  res = 0
  i = 1 # Инициализация условной переменной

  # Циклическое суммирование 1, 4, 10, ...
  while i <= n
    res += i
    # Обновить условную переменную
    i += 1
    i *= 2
  end

  res
end
Визуализация кода

В целом код с использованием цикла for более компактный, а цикл while более гибкий. Но они оба могут реализовать итерационную структуру. Выбор между ними определяется требованиями конкретной задачи.

3.   Вложенные циклы

Внутрь одной циклической структуры можно вложить другую, например используя два цикла for :

iteration.py
def nested_for_loop(n: int) -> str:
    """Двойной цикл for"""
    res = ""
    # Цикл по i = 1, 2, ..., n-1, n
    for i in range(1, n + 1):
        # Цикл по j = 1, 2, ..., n-1, n
        for j in range(1, n + 1):
            res += f"({i}, {j}), "
    return res
iteration.cpp
/* Двойной цикл for */
string nestedForLoop(int n) {
    ostringstream res;
    // Цикл по i = 1, 2, ..., n-1, n
    for (int i = 1; i <= n; ++i) {
        // Цикл по j = 1, 2, ..., n-1, n
        for (int j = 1; j <= n; ++j) {
            res << "(" << i << ", " << j << "), ";
        }
    }
    return res.str();
}
iteration.java
/* Двойной цикл for */
String nestedForLoop(int n) {
    StringBuilder res = new StringBuilder();
    // Цикл по i = 1, 2, ..., n-1, n
    for (int i = 1; i <= n; i++) {
        // Цикл по j = 1, 2, ..., n-1, n
        for (int j = 1; j <= n; j++) {
            res.append("(" + i + ", " + j + "), ");
        }
    }
    return res.toString();
}
iteration.cs
/* Двойной цикл for */
string NestedForLoop(int n) {
    StringBuilder res = new();
    // Цикл по i = 1, 2, ..., n-1, n
    for (int i = 1; i <= n; i++) {
        // Цикл по j = 1, 2, ..., n-1, n
        for (int j = 1; j <= n; j++) {
            res.Append($"({i}, {j}), ");
        }
    }
    return res.ToString();
}
iteration.go
/* Двойной цикл for */
func nestedForLoop(n int) string {
    res := ""
    // Цикл по i = 1, 2, ..., n-1, n
    for i := 1; i <= n; i++ {
        for j := 1; j <= n; j++ {
            // Цикл по j = 1, 2, ..., n-1, n
            res += fmt.Sprintf("(%d, %d), ", i, j)
        }
    }
    return res
}
iteration.swift
/* Двойной цикл for */
func nestedForLoop(n: Int) -> String {
    var res = ""
    // Цикл по i = 1, 2, ..., n-1, n
    for i in 1 ... n {
        // Цикл по j = 1, 2, ..., n-1, n
        for j in 1 ... n {
            res.append("(\(i), \(j)), ")
        }
    }
    return res
}
iteration.js
/* Двойной цикл for */
function nestedForLoop(n) {
    let res = '';
    // Цикл по i = 1, 2, ..., n-1, n
    for (let i = 1; i <= n; i++) {
        // Цикл по j = 1, 2, ..., n-1, n
        for (let j = 1; j <= n; j++) {
            res += `(${i}, ${j}), `;
        }
    }
    return res;
}
iteration.ts
/* Двойной цикл for */
function nestedForLoop(n: number): string {
    let res = '';
    // Цикл по i = 1, 2, ..., n-1, n
    for (let i = 1; i <= n; i++) {
        // Цикл по j = 1, 2, ..., n-1, n
        for (let j = 1; j <= n; j++) {
            res += `(${i}, ${j}), `;
        }
    }
    return res;
}
iteration.dart
/* Двойной цикл for */
String nestedForLoop(int n) {
  String res = "";
  // Цикл по i = 1, 2, ..., n-1, n
  for (int i = 1; i <= n; i++) {
    // Цикл по j = 1, 2, ..., n-1, n
    for (int j = 1; j <= n; j++) {
      res += "($i, $j), ";
    }
  }
  return res;
}
iteration.rs
/* Двойной цикл for */
fn nested_for_loop(n: i32) -> String {
    let mut res = vec![];
    // Цикл по i = 1, 2, ..., n-1, n
    for i in 1..=n {
        // Цикл по j = 1, 2, ..., n-1, n
        for j in 1..=n {
            res.push(format!("({}, {}), ", i, j));
        }
    }
    res.join("")
}
iteration.c
/* Двойной цикл for */
char *nestedForLoop(int n) {
    // n * n — это число соответствующих точек, а максимальная длина строки "(i, j), " равна 6+10*2, плюс дополнительное место для завершающего нулевого символа \0
    int size = n * n * 26 + 1;
    char *res = malloc(size * sizeof(char));
    // Цикл по i = 1, 2, ..., n-1, n
    for (int i = 1; i <= n; i++) {
        // Цикл по j = 1, 2, ..., n-1, n
        for (int j = 1; j <= n; j++) {
            char tmp[26];
            snprintf(tmp, sizeof(tmp), "(%d, %d), ", i, j);
            strncat(res, tmp, size - strlen(res) - 1);
        }
    }
    return res;
}
iteration.kt
/* Двойной цикл for */
fun nestedForLoop(n: Int): String {
    val res = StringBuilder()
    // Цикл по i = 1, 2, ..., n-1, n
    for (i in 1..n) {
        // Цикл по j = 1, 2, ..., n-1, n
        for (j in 1..n) {
            res.append(" ($i, $j), ")
        }
    }
    return res.toString()
}
iteration.rb
### Двойной цикл for ###
def nested_for_loop(n)
  res = ""

  # Цикл по i = 1, 2, ..., n-1, n
  for i in 1..n
    # Цикл по j = 1, 2, ..., n-1, n
    for j in 1..n
      res += "(#{i}, #{j}), "
    end
  end

  res
end
Визуализация кода

На рисунке 2-2 приведена блок-схема такого вложенного цикла.

Блок-схема вложенного цикла

Рисунок 2-2   Блок-схема вложенного цикла

В этом случае количество выполненных действий пропорционально \(n^2\) , или, другими словами, время выполнения алгоритма и размер входных данных \(n\) находятся в квадратичной зависимости.

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

2.2.2   Рекурсия

Рекурсия (recursion) - это стратегия алгоритма, при которой функция вызывает саму себя для решения задачи. Она включает два основных этапа.

  1. Вызов: программа постоянно вызывает саму себя, обычно передавая меньшие или более упрощенные параметры, пока не будет достигнуто условие завершения.
  2. Возврат: после срабатывания условия завершения программа начинает возвращаться из самой глубокой рекурсивной функции, объединяя результаты каждого уровня.

С точки зрения реализации рекурсивный код включает три основных элемента.

  1. Условие завершения: используется для определения момента перехода от вызова к возврату.
  2. Рекурсивный вызов: соответствует вызову, функция вызывает саму себя, обычно с меньшими или упрощенными параметрами.
  3. Возврат результата: соответствует возврату, возвращает результат текущего уровня рекурсии на предыдущий уровень.

Рассмотрим следующий код: вызов функции recur(n) позволяет вычислить сумму \(1 + 2 + \dots + n\) :

recursion.py
def recur(n: int) -> int:
    """Рекурсия"""
    # Условие завершения
    if n == 1:
        return 1
    # Рекурсия: рекурсивный вызов
    res = recur(n - 1)
    # Возврат: вернуть результат
    return n + res
recursion.cpp
/* Рекурсия */
int recur(int n) {
    // Условие завершения
    if (n == 1)
        return 1;
    // Рекурсия: рекурсивный вызов
    int res = recur(n - 1);
    // Возврат: вернуть результат
    return n + res;
}
recursion.java
/* Рекурсия */
int recur(int n) {
    // Условие завершения
    if (n == 1)
        return 1;
    // Рекурсия: рекурсивный вызов
    int res = recur(n - 1);
    // Возврат: вернуть результат
    return n + res;
}
recursion.cs
/* Рекурсия */
int Recur(int n) {
    // Условие завершения
    if (n == 1)
        return 1;
    // Рекурсия: рекурсивный вызов
    int res = Recur(n - 1);
    // Возврат: вернуть результат
    return n + res;
}
recursion.go
/* Рекурсия */
func recur(n int) int {
    // Условие завершения
    if n == 1 {
        return 1
    }
    // Рекурсия: рекурсивный вызов
    res := recur(n - 1)
    // Возврат: вернуть результат
    return n + res
}
recursion.swift
/* Рекурсия */
func recur(n: Int) -> Int {
    // Условие завершения
    if n == 1 {
        return 1
    }
    // Рекурсия: рекурсивный вызов
    let res = recur(n: n - 1)
    // Возврат: вернуть результат
    return n + res
}
recursion.js
/* Рекурсия */
function recur(n) {
    // Условие завершения
    if (n === 1) return 1;
    // Рекурсия: рекурсивный вызов
    const res = recur(n - 1);
    // Возврат: вернуть результат
    return n + res;
}
recursion.ts
/* Рекурсия */
function recur(n: number): number {
    // Условие завершения
    if (n === 1) return 1;
    // Рекурсия: рекурсивный вызов
    const res = recur(n - 1);
    // Возврат: вернуть результат
    return n + res;
}
recursion.dart
/* Рекурсия */
int recur(int n) {
  // Условие завершения
  if (n == 1) return 1;
  // Рекурсия: рекурсивный вызов
  int res = recur(n - 1);
  // Возврат: вернуть результат
  return n + res;
}
recursion.rs
/* Рекурсия */
fn recur(n: i32) -> i32 {
    // Условие завершения
    if n == 1 {
        return 1;
    }
    // Рекурсия: рекурсивный вызов
    let res = recur(n - 1);
    // Возврат: вернуть результат
    n + res
}
recursion.c
/* Рекурсия */
int recur(int n) {
    // Условие завершения
    if (n == 1)
        return 1;
    // Рекурсия: рекурсивный вызов
    int res = recur(n - 1);
    // Возврат: вернуть результат
    return n + res;
}
recursion.kt
/* Рекурсия */
fun recur(n: Int): Int {
    // Условие завершения
    if (n == 1)
        return 1
    // Рекурсивный шаг: рекурсивный вызов
    val res = recur(n - 1)
    // Возврат: вернуть результат
    return n + res
}
recursion.rb
### Рекурсия ###
def recur(n)
  # Условие завершения
  return 1 if n == 1
  # Рекурсия: рекурсивный вызов
  res = recur(n - 1)
  # Возврат: вернуть результат
  n + res
end
Визуализация кода

На рисунке 2-3 представлен рекурсивный процесс этой функции.

Рекурсивный процесс функции суммирования

Рисунок 2-3   Рекурсивный процесс функции суммирования

Хотя с точки зрения вычислений итерация и рекурсия могут давать одинаковый результат, они представляют собой совершенно разные парадигмы мышления и решения задач.

  • Итерация: решение задачи снизу вверх. Начинаем с самых базовых шагов, которые затем повторяются или накапливаются до завершения задачи.
  • Рекурсия: решение задачи сверху вниз. Исходная задача разбивается на более мелкие подзадачи, которые имеют ту же форму, что и исходная задача. Далее подзадачи продолжают делиться на еще более мелкие, пока не достигается базовый случай, решение которого известно.

Рассмотрим в качестве примера вышеупомянутую функцию суммирования, где решается задача \(f(n) = 1 + 2 + \dots + n\) .

  • Итерация: моделирование процесса суммирования в цикле проходит от \(1\) до \(n\) , выполняя операцию суммирования на каждом шаге, чтобы получить итоговое значение \(f(n)\) .
  • Рекурсия: последовательное разбиение задачи на подзадачи вида \(f(n) = n + f(n - 1)\) до достижения базового случая \(f(1) = 1\) .

1.   Стек вызовов

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

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

Как показано на рисунке 2-4, до срабатывания условия завершения одновременно существует \(n\) невозвращенных рекурсивных функций, а глубина рекурсии равна \(n\) .

Глубина рекурсивного вызова

Рисунок 2-4   Глубина рекурсивного вызова

На практике глубина рекурсии, разрешенная языком программирования, обычно ограничена, и слишком глубокая рекурсия может привести к ошибке переполнения стека.

2.   Хвостовая рекурсия

Интересно, что если рекурсивный вызов происходит на последнем шаге перед возвратом функции , то компилятор или интерпретатор может оптимизировать этот вызов, сделав его по эффективности использования памяти сопоставимым с итерацией. Это называется хвостовой рекурсией (tail recursion).

  • Обычная рекурсия: когда функция возвращается на предыдущий уровень, необходимо продолжить выполнение кода, поэтому системе нужно сохранить контекст предыдущего вызова.
  • Хвостовая рекурсия: рекурсивный вызов является последней операцией перед возвратом функции, что означает, что после возврата на предыдущий уровень не требуется выполнять другие операции, поэтому системе не нужно сохранять контекст предыдущей функции.

В качестве примера вычисления суммы \(1 + 2 + \dots + n\) можно установить переменную результата res в качестве параметра функции, чтобы реализовать хвостовую рекурсию:

recursion.py
def tail_recur(n, res):
    """Хвостовая рекурсия"""
    # Условие завершения
    if n == 0:
        return res
    # Хвостовой рекурсивный вызов
    return tail_recur(n - 1, res + n)
recursion.cpp
/* Хвостовая рекурсия */
int tailRecur(int n, int res) {
    // Условие завершения
    if (n == 0)
        return res;
    // Хвостовой рекурсивный вызов
    return tailRecur(n - 1, res + n);
}
recursion.java
/* Хвостовая рекурсия */
int tailRecur(int n, int res) {
    // Условие завершения
    if (n == 0)
        return res;
    // Хвостовой рекурсивный вызов
    return tailRecur(n - 1, res + n);
}
recursion.cs
/* Хвостовая рекурсия */
int TailRecur(int n, int res) {
    // Условие завершения
    if (n == 0)
        return res;
    // Хвостовой рекурсивный вызов
    return TailRecur(n - 1, res + n);
}
recursion.go
/* Хвостовая рекурсия */
func tailRecur(n int, res int) int {
    // Условие завершения
    if n == 0 {
        return res
    }
    // Хвостовой рекурсивный вызов
    return tailRecur(n-1, res+n)
}
recursion.swift
/* Хвостовая рекурсия */
func tailRecur(n: Int, res: Int) -> Int {
    // Условие завершения
    if n == 0 {
        return res
    }
    // Хвостовой рекурсивный вызов
    return tailRecur(n: n - 1, res: res + n)
}
recursion.js
/* Хвостовая рекурсия */
function tailRecur(n, res) {
    // Условие завершения
    if (n === 0) return res;
    // Хвостовой рекурсивный вызов
    return tailRecur(n - 1, res + n);
}
recursion.ts
/* Хвостовая рекурсия */
function tailRecur(n: number, res: number): number {
    // Условие завершения
    if (n === 0) return res;
    // Хвостовой рекурсивный вызов
    return tailRecur(n - 1, res + n);
}
recursion.dart
/* Хвостовая рекурсия */
int tailRecur(int n, int res) {
  // Условие завершения
  if (n == 0) return res;
  // Хвостовой рекурсивный вызов
  return tailRecur(n - 1, res + n);
}
recursion.rs
/* Хвостовая рекурсия */
fn tail_recur(n: i32, res: i32) -> i32 {
    // Условие завершения
    if n == 0 {
        return res;
    }
    // Хвостовой рекурсивный вызов
    tail_recur(n - 1, res + n)
}
recursion.c
/* Хвостовая рекурсия */
int tailRecur(int n, int res) {
    // Условие завершения
    if (n == 0)
        return res;
    // Хвостовой рекурсивный вызов
    return tailRecur(n - 1, res + n);
}
recursion.kt
/* Хвостовая рекурсия */
tailrec fun tailRecur(n: Int, res: Int): Int {
    // Добавить ключевое слово tailrec, чтобы включить оптимизацию хвостовой рекурсии
    // Условие завершения
    if (n == 0)
        return res
    // Хвостовой рекурсивный вызов
    return tailRecur(n - 1, res + n)
}
recursion.rb
### Хвостовая рекурсия ###
def tail_recur(n, res)
  # Условие завершения
  return res if n == 0
  # Хвостовой рекурсивный вызов
  tail_recur(n - 1, res + n)
end
Визуализация кода

Процесс выполнения хвостовой рекурсии показан на рисунке 2-5. Сравнивая обычную и хвостовую рекурсии, можно заметить, что точка выполнения операции суммирования у них различается.

  • Обычная рекурсия: операция суммирования выполняется в процессе возврата, после каждого возврата необходимо снова выполнить операцию суммирования.
  • Хвостовая рекурсия: операция суммирования выполняется в процессе вызова, а процесс возврата требует только последовательного возврата.

Процесс хвостовой рекурсии

Рисунок 2-5   Процесс хвостовой рекурсии

Tip

Обратите внимание: многие компиляторы и интерпретаторы не поддерживают оптимизацию хвостовой рекурсии. Например, Python по умолчанию такую оптимизацию не выполняет, поэтому даже функция в хвостово-рекурсивной форме все равно может привести к переполнению стека.

3.   Дерево рекурсии

При решении задач, связанных с алгоритмами типа «разделяй и властвуй», рекурсия часто оказывается более интуитивной и читабельной, чем итерация. Рассмотрим в качестве примера последовательность Фибоначчи.

Question

Дана последовательность Фибоначчи \(0, 1, 1, 2, 3, 5, 8, 13, \dots\). Найди \(n\)-й элемент этой последовательности.

Обозначив \(n\)-й член последовательности Фибоначчи как \(f(n)\) , можно сформулировать два утверждения.

  • Первые два числа последовательности: \(f(1) = 0\) и \(f(2) = 1\) .
  • Каждое число последовательности является суммой двух предыдущих чисел, то есть \(f(n) = f(n - 1) + f(n - 2)\) .

Используя рекурсивные вызовы в соответствии с рекуррентным соотношением и принимая первые два числа за условия остановки, можно написать рекурсивный код. Вызов fib(n) позволит получить \(n\)-й член последовательности Фибоначчи:

recursion.py
def fib(n: int) -> int:
    """Последовательность Фибоначчи: рекурсия"""
    # Условие завершения: f(1) = 0, f(2) = 1
    if n == 1 or n == 2:
        return n - 1
    # Рекурсивный вызов f(n) = f(n-1) + f(n-2)
    res = fib(n - 1) + fib(n - 2)
    # Вернуть результат f(n)
    return res
recursion.cpp
/* Последовательность Фибоначчи: рекурсия */
int fib(int n) {
    // Условие завершения: f(1) = 0, f(2) = 1
    if (n == 1 || n == 2)
        return n - 1;
    // Рекурсивный вызов f(n) = f(n-1) + f(n-2)
    int res = fib(n - 1) + fib(n - 2);
    // Вернуть результат f(n)
    return res;
}
recursion.java
/* Последовательность Фибоначчи: рекурсия */
int fib(int n) {
    // Условие завершения: f(1) = 0, f(2) = 1
    if (n == 1 || n == 2)
        return n - 1;
    // Рекурсивный вызов f(n) = f(n-1) + f(n-2)
    int res = fib(n - 1) + fib(n - 2);
    // Вернуть результат f(n)
    return res;
}
recursion.cs
/* Последовательность Фибоначчи: рекурсия */
int Fib(int n) {
    // Условие завершения: f(1) = 0, f(2) = 1
    if (n == 1 || n == 2)
        return n - 1;
    // Рекурсивный вызов f(n) = f(n-1) + f(n-2)
    int res = Fib(n - 1) + Fib(n - 2);
    // Вернуть результат f(n)
    return res;
}
recursion.go
/* Последовательность Фибоначчи: рекурсия */
func fib(n int) int {
    // Условие завершения: f(1) = 0, f(2) = 1
    if n == 1 || n == 2 {
        return n - 1
    }
    // Рекурсивный вызов f(n) = f(n-1) + f(n-2)
    res := fib(n-1) + fib(n-2)
    // Вернуть результат f(n)
    return res
}
recursion.swift
/* Последовательность Фибоначчи: рекурсия */
func fib(n: Int) -> Int {
    // Условие завершения: f(1) = 0, f(2) = 1
    if n == 1 || n == 2 {
        return n - 1
    }
    // Рекурсивный вызов f(n) = f(n-1) + f(n-2)
    let res = fib(n: n - 1) + fib(n: n - 2)
    // Вернуть результат f(n)
    return res
}
recursion.js
/* Последовательность Фибоначчи: рекурсия */
function fib(n) {
    // Условие завершения: f(1) = 0, f(2) = 1
    if (n === 1 || n === 2) return n - 1;
    // Рекурсивный вызов f(n) = f(n-1) + f(n-2)
    const res = fib(n - 1) + fib(n - 2);
    // Вернуть результат f(n)
    return res;
}
recursion.ts
/* Последовательность Фибоначчи: рекурсия */
function fib(n: number): number {
    // Условие завершения: f(1) = 0, f(2) = 1
    if (n === 1 || n === 2) return n - 1;
    // Рекурсивный вызов f(n) = f(n-1) + f(n-2)
    const res = fib(n - 1) + fib(n - 2);
    // Вернуть результат f(n)
    return res;
}
recursion.dart
/* Последовательность Фибоначчи: рекурсия */
int fib(int n) {
  // Условие завершения: f(1) = 0, f(2) = 1
  if (n == 1 || n == 2) return n - 1;
  // Рекурсивный вызов f(n) = f(n-1) + f(n-2)
  int res = fib(n - 1) + fib(n - 2);
  // Вернуть результат f(n)
  return res;
}
recursion.rs
/* Последовательность Фибоначчи: рекурсия */
fn fib(n: i32) -> i32 {
    // Условие завершения: f(1) = 0, f(2) = 1
    if n == 1 || n == 2 {
        return n - 1;
    }
    // Рекурсивный вызов f(n) = f(n-1) + f(n-2)
    let res = fib(n - 1) + fib(n - 2);
    // Вернуть результат
    res
}
recursion.c
/* Последовательность Фибоначчи: рекурсия */
int fib(int n) {
    // Условие завершения: f(1) = 0, f(2) = 1
    if (n == 1 || n == 2)
        return n - 1;
    // Рекурсивный вызов f(n) = f(n-1) + f(n-2)
    int res = fib(n - 1) + fib(n - 2);
    // Вернуть результат f(n)
    return res;
}
recursion.kt
/* Последовательность Фибоначчи: рекурсия */
fun fib(n: Int): Int {
    // Условие завершения: f(1) = 0, f(2) = 1
    if (n == 1 || n == 2)
        return n - 1
    // Рекурсивный вызов f(n) = f(n-1) + f(n-2)
    val res = fib(n - 1) + fib(n - 2)
    // Вернуть результат f(n)
    return res
}
recursion.rb
### Последовательность Фибоначчи: рекурсия ###
def fib(n)
  # Условие завершения: f(1) = 0, f(2) = 1
  return n - 1 if n == 1 || n == 2
  # Рекурсивный вызов f(n) = f(n-1) + f(n-2)
  res = fib(n - 1) + fib(n - 2)
  # Вернуть результат f(n)
  res
end
Визуализация кода

Проанализировав приведенный код, можно заметить, что внутри функции осуществляется рекурсивный вызов двух функций, то есть из одного вызова образуются два ветвления. Как показано на рисунке 2-6, при последующем выполнении рекурсивных вызовов в итоге образуется дерево рекурсии (recursion tree) глубиной \(n\) .

Дерево рекурсии последовательности Фибоначчи

Рисунок 2-6   Дерево рекурсии последовательности Фибоначчи

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

  • С точки зрения алгоритмов многие важные алгоритмические стратегии, такие как поиск, сортировка, возврат, «разделяй и властвуй» и динамическое программирование, прямо или косвенно используют этот подход.
  • С точки зрения структур данных рекурсия естественно подходит для решения задач, связанных со списками, деревьями и графами, поскольку они очень хорошо поддаются анализу с использованием идеи «разделяй и властвуй».

2.2.3   Сравнение

Подводя итог, можно сказать, что итерация и рекурсия различаются по реализации, производительности и применимости, как показано в таблице 2-1.

Таблица 2-1   Сравнение итерации и рекурсии

Итерация Рекурсия
Способ реализации Циклическая структура Функция вызывает саму себя
Временная эффективность Обычно высокая эффективность, нет затрат на вызов функции Каждый вызов функции создает затраты
Использование памяти Обычно используется фиксированный объем памяти Накопление вызовов функции может использовать значительное количество пространства стека
Сфера использования Подходит для простых циклических задач, код интуитивно понятен и хорошо читаем Подходит для разбиения на подзадачи, для структур деревья и графы, алгоритмов «разделяй и властвуй», возврата и т. д.. Структура кода проста и ясна

Tip

Если дальнейшее содержание кажется сложным, можно вернуться к нему после чтения главы о «стеке».

Какова же внутренняя связь между итерацией и рекурсией? В рассмотренном примере рекурсивной функции операция сложения выполняется на этапе возврата рекурсии. Это означает, что функция, вызванная первой, фактически завершает операцию сложения последней, что соответствует принципу стека «первым пришел - последним вышел».

На самом деле такие термины рекурсии, как «стек вызовов» и «пространство стекового кадра», уже намекают на тесную связь между рекурсией и стеком.

  1. Вызов: когда вызывается функция, система выделяет для нее новый стековый кадр в «стеке вызовов» для хранения локальных переменных функции, параметров, адреса возврата и других данных.
  2. Возврат: когда функция завершает выполнение и возвращает результат, соответствующий стековый кадр удаляется из «стека вызовов», восстанавливая среду выполнения предыдущей функции.

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

recursion.py
def for_loop_recur(n: int) -> int:
    """Имитация рекурсии итерацией"""
    # Использовать явный стек для имитации системного стека вызовов
    stack = []
    res = 0
    # Рекурсия: рекурсивный вызов
    for i in range(n, 0, -1):
        # Имитировать «рекурсию» с помощью операции помещения в стек
        stack.append(i)
    # Возврат: вернуть результат
    while stack:
        # Имитировать «возврат» с помощью операции извлечения из стека
        res += stack.pop()
    # res = 1+2+3+...+n
    return res
recursion.cpp
/* Имитация рекурсии итерацией */
int forLoopRecur(int n) {
    // Использовать явный стек для имитации системного стека вызовов
    stack<int> stack;
    int res = 0;
    // Рекурсия: рекурсивный вызов
    for (int i = n; i > 0; i--) {
        // Имитировать «рекурсию» с помощью операции помещения в стек
        stack.push(i);
    }
    // Возврат: вернуть результат
    while (!stack.empty()) {
        // Имитировать «возврат» с помощью операции извлечения из стека
        res += stack.top();
        stack.pop();
    }
    // res = 1+2+3+...+n
    return res;
}
recursion.java
/* Имитация рекурсии итерацией */
int forLoopRecur(int n) {
    // Использовать явный стек для имитации системного стека вызовов
    Stack<Integer> stack = new Stack<>();
    int res = 0;
    // Рекурсия: рекурсивный вызов
    for (int i = n; i > 0; i--) {
        // Имитировать «рекурсию» с помощью операции помещения в стек
        stack.push(i);
    }
    // Возврат: вернуть результат
    while (!stack.isEmpty()) {
        // Имитировать «возврат» с помощью операции извлечения из стека
        res += stack.pop();
    }
    // res = 1+2+3+...+n
    return res;
}
recursion.cs
/* Имитация рекурсии итерацией */
int ForLoopRecur(int n) {
    // Использовать явный стек для имитации системного стека вызовов
    Stack<int> stack = new();
    int res = 0;
    // Рекурсия: рекурсивный вызов
    for (int i = n; i > 0; i--) {
        // Имитировать «рекурсию» с помощью операции помещения в стек
        stack.Push(i);
    }
    // Возврат: вернуть результат
    while (stack.Count > 0) {
        // Имитировать «возврат» с помощью операции извлечения из стека
        res += stack.Pop();
    }
    // res = 1+2+3+...+n
    return res;
}
recursion.go
/* Имитация рекурсии итерацией */
func forLoopRecur(n int) int {
    // Использовать явный стек для имитации системного стека вызовов
    stack := list.New()
    res := 0
    // Рекурсия: рекурсивный вызов
    for i := n; i > 0; i-- {
        // Имитировать «рекурсию» с помощью операции помещения в стек
        stack.PushBack(i)
    }
    // Возврат: вернуть результат
    for stack.Len() != 0 {
        // Имитировать «возврат» с помощью операции извлечения из стека
        res += stack.Back().Value.(int)
        stack.Remove(stack.Back())
    }
    // res = 1+2+3+...+n
    return res
}
recursion.swift
/* Имитация рекурсии итерацией */
func forLoopRecur(n: Int) -> Int {
    // Использовать явный стек для имитации системного стека вызовов
    var stack: [Int] = []
    var res = 0
    // Рекурсия: рекурсивный вызов
    for i in (1 ... n).reversed() {
        // Имитировать «рекурсию» с помощью операции помещения в стек
        stack.append(i)
    }
    // Возврат: вернуть результат
    while !stack.isEmpty {
        // Имитировать «возврат» с помощью операции извлечения из стека
        res += stack.removeLast()
    }
    // res = 1+2+3+...+n
    return res
}
recursion.js
/* Имитация рекурсии итерацией */
function forLoopRecur(n) {
    // Использовать явный стек для имитации системного стека вызовов
    const stack = [];
    let res = 0;
    // Рекурсия: рекурсивный вызов
    for (let i = n; i > 0; i--) {
        // Имитировать «рекурсию» с помощью операции помещения в стек
        stack.push(i);
    }
    // Возврат: вернуть результат
    while (stack.length) {
        // Имитировать «возврат» с помощью операции извлечения из стека
        res += stack.pop();
    }
    // res = 1+2+3+...+n
    return res;
}
recursion.ts
/* Имитация рекурсии итерацией */
function forLoopRecur(n: number): number {
    // Использовать явный стек для имитации системного стека вызовов
    const stack: number[] = [];
    let res: number = 0;
    // Рекурсия: рекурсивный вызов
    for (let i = n; i > 0; i--) {
        // Имитировать «рекурсию» с помощью операции помещения в стек
        stack.push(i);
    }
    // Возврат: вернуть результат
    while (stack.length) {
        // Имитировать «возврат» с помощью операции извлечения из стека
        res += stack.pop();
    }
    // res = 1+2+3+...+n
    return res;
}
recursion.dart
/* Имитация рекурсии итерацией */
int forLoopRecur(int n) {
  // Использовать явный стек для имитации системного стека вызовов
  List<int> stack = [];
  int res = 0;
  // Рекурсия: рекурсивный вызов
  for (int i = n; i > 0; i--) {
    // Имитировать «рекурсию» с помощью операции помещения в стек
    stack.add(i);
  }
  // Возврат: вернуть результат
  while (!stack.isEmpty) {
    // Имитировать «возврат» с помощью операции извлечения из стека
    res += stack.removeLast();
  }
  // res = 1+2+3+...+n
  return res;
}
recursion.rs
/* Имитация рекурсии итерацией */
fn for_loop_recur(n: i32) -> i32 {
    // Использовать явный стек для имитации системного стека вызовов
    let mut stack = Vec::new();
    let mut res = 0;
    // Рекурсия: рекурсивный вызов
    for i in (1..=n).rev() {
        // Имитировать «рекурсию» с помощью операции помещения в стек
        stack.push(i);
    }
    // Возврат: вернуть результат
    while !stack.is_empty() {
        // Имитировать «возврат» с помощью операции извлечения из стека
        res += stack.pop().unwrap();
    }
    // res = 1+2+3+...+n
    res
}
recursion.c
/* Имитация рекурсии итерацией */
int forLoopRecur(int n) {
    int stack[1000]; // Использовать большой массив для имитации стека
    int top = -1;    // Индекс вершины стека
    int res = 0;
    // Рекурсия: рекурсивный вызов
    for (int i = n; i > 0; i--) {
        // Имитировать «рекурсию» с помощью операции помещения в стек
        stack[1 + top++] = i;
    }
    // Возврат: вернуть результат
    while (top >= 0) {
        // Имитировать «возврат» с помощью операции извлечения из стека
        res += stack[top--];
    }
    // res = 1+2+3+...+n
    return res;
}
recursion.kt
/* Имитация рекурсии итерацией */
fun forLoopRecur(n: Int): Int {
    // Использовать явный стек для имитации системного стека вызовов
    val stack = Stack<Int>()
    var res = 0
    // Рекурсивный шаг: рекурсивный вызов
    for (i in n downTo 0) {
        // Имитировать «рекурсию» с помощью операции помещения в стек
        stack.push(i)
    }
    // Возврат: вернуть результат
    while (stack.isNotEmpty()) {
        // Имитировать «возврат» с помощью операции извлечения из стека
        res += stack.pop()
    }
    // res = 1+2+3+...+n
    return res
}
recursion.rb
### Имитация рекурсии итерацией ###
def for_loop_recur(n)
  # Использовать явный стек для имитации системного стека вызовов
  stack = []
  res = 0

  # Рекурсия: рекурсивный вызов
  for i in n.downto(0)
    # Имитировать «рекурсию» с помощью операции помещения в стек
    stack << i
  end
  # Возврат: вернуть результат
  while !stack.empty?
    res += stack.pop
  end

  # res = 1+2+3+...+n
  res
end
Визуализация кода

Наблюдая за приведенным выше кодом, можно заметить, что после преобразования рекурсии в итерацию код становится более сложным. Хотя во многих случаях итерация и рекурсия действительно могут быть преобразованы друг в друга, это не всегда стоит делать по двум причинам.

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

Итак, выбор между итерацией и рекурсией зависит от природы конкретной задачи. В практическом программировании крайне важно взвешивать преимущества и недостатки обоих подходов и выбирать подходящий метод с учетом контекста.

Оставляйте свои идеи, вопросы и предложения в комментариях