В этой статье мы собираемся объяснить концепцию рекурсии. Прежде всего, мы увидим, что такое рекурсия в программировании, как работает рекурсия, как компьютер управляет этой концепцией, а затем два примера: _sum_recursion и _pow_recursion. Для этого мы будем использовать некоторые фрагменты кода на языке C (наслаждайтесь!).

Что такое рекурсия в программировании?

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

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

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

Мы можем сравнить это с вложенными циклами: цикл в цикле в цикле в цикле и т. д. Это то же самое: функция, которая вызывает себя, вызывает себя, вызывает себя и т. д.

Действительно, как это работает?

Как работает рекурсия?

Для каждого рекурсивного алгоритма есть два основных шага:

  1. Условие остановки
  2. Рекурсивный вызов

Шаг 1. Условие остановки:

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

Шаг 2 — рекурсивный вызов:

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

Но как компьютер справляется с этой концепцией?

Как компьютер управляет рекурсией?

Рекурсия использует реализацию stack. В программировании stack — это структура данных, которой можно манипулировать с помощью pushing (добавление) и popping (удаление) данных в верхней части списка. На самом деле стек означает Last In First Out.

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

Хорошо, но можем ли мы увидеть несколько примеров? Да пошли!

_sum_recursion:

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

1  int main(void)
2  {
3      int result;
4
5      result = _sum_recursion(3);
6      return (result);
7  }
8
9  int _sum_recursion(int n)
10 {
11     if (n != 0)
12         return (n + _sum_recursion(n - 1));
13     return (n);
14 }

Описание флага:

  • строка 5: основной вызов функции _sum_recursion(3) с n = 3
  • строка 6: вернуть результат рекурсивной функции
  • строка 9: рекурсивная функция суммирования, принимающая один аргумент int n
  • строка 11: условие остановки, это означает, что рекурсия остановится, когда значение n = 0
  • строка 12: рекурсивный вызов, функция возвращает значение n + _sum_recursion(n-1), если условие остановки равно True
  • строка 13: функция возвращает значение n, когда условие False

Рабочий процесс выглядит следующим образом:

  • T01: основная функция вызывает _sum_recursion и передает значение n = 3
  • T02: время выполнения _sum_recursion начинается с n = 3

=> В стек добавляется вызов _sum_recursion(3) и сам вызов функции.

  • T03: if (n != 0) ? да, это правда
  • T04: return (3 + _sum_recursion(3-1))

=> В стек добавляется вызов _sum_recursion(2) и сам вызов функции.

  • T05: сейчас n = 2
  • T06: if (n != 0) ? да, это правда
  • T07: return (2 + _sum_recursion(2-1))

=> В стек добавляется вызов _sum_recursion(1) и сам вызов функции.

  • T08: сейчас n = 1
  • T09: if (n != 0) ? да, это правда
  • T10: return (1 + _sum_recursion(1-1))

=> В стек добавляется вызов _sum_recursion(0) и сам вызов функции.

  • T11: сейчас n = 0
  • T12: if (n != 0) ? Нет, это ложь
  • T13: return (0)

=› Рекурсия остановилась и пришло время вернуть значение в основную функцию. Последний вызов, добавленный в стек, — это первое значение, возвращаемое предыдущим вызовам:

Глобальная схема:

_pow_recursion:

Для этого второго примера мы выбираем функцию pow-рекурсии, которая принимает два целых числа x и y. И возвращает результат x в степени y. Здесь условие остановки — это когда y == 0 .

Ниже мы объясним два основных случая:

Случай 1: y > 0

1  float main(void)
2  {
3      float result;
4
5      result = _pow_recursion(2, 2);
6      return (result);
7  }
8
9  float _pow_recursion(float x, float y)
10 {
11     if (y == 0)
12         return (1);
13     if (y < 0)
14         return (_pow_recursion(x, y + 1) / x);
15     return (_pow_recursion(x, y - 1) * x);
16 }

Рабочий процесс в стеке:

Глобальная схема:

Случай 2: y < 0

1  float main(void)
2  {
3      float result;
4
5      result = _pow_recursion(2, -2);
6      return (result);
7  }
8
9  float _pow_recursion(float x, float y)
10 {
11     if (y == 0)
12         return (1);
13     if (y < 0)
14         return (_pow_recursion(x, y + 1) / x);
15     return (_pow_recursion(x, y - 1) * x);
16 }

Рабочий процесс в стеке:

Глобальная схема:

Заключение

Функции рекурсии делают программы элегантными и уменьшают временную сложность (большой O).

Недостатки рекурсии связаны с накладными расходами на поддержку стека и требуют большего объема памяти. Временная сложность рекурсии O(n) .

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

Если вы хотите увидеть продвинутое использование рекурсии, изучите алгоритм сортировки.

Я надеюсь, что эта статья была полезной. Спасибо за прочтение!

Написано Элоди для Holberton School LVA.