Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 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\) :

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
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` :

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
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` :

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
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` :

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
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\) :

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
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` в качестве параметра функции, чтобы реализовать хвостовую рекурсию:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
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\)-й член последовательности Фибоначчи:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
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. Возврат: когда функция завершает выполнение и возвращает результат, соответствующий стековый кадр удаляется из «стека вызовов», восстанавливая среду выполнения предыдущей функции.

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

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
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

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

Во весь экран >

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

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

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

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