Рекурсия - как переполнить стек и как не делать этого

В одном из моих предыдущих блогов мы создали рекурсивную функцию. Рекурсивные функции - это функции, которые вызывают сами себя. Если вы новичок в рекурсивной функции, это могло повредить вашему мозгу. Сегодняшний блог находится в таких же строках. Это может помочь вам лучше понять рекурсию.

Веселое упражнение: попробуйте поискать слово "рекурсия" в Google.

Мы создадим рекурсивную функцию, чтобы найти факториал числа. Факториал числа - это произведение всех целых чисел перед ним вниз до 1. Факториал 1 равен 1. И это базовый случай.

let rec fact x =
 if x <= 1 then 1
 else
  x * fact (x-1)

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

Что такое стек вызовов?

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

В названии этого блога я использую слово «стек». В этом блоге я использую стек и стек вызовов как взаимозаменяемые. Стек вызовов состоит из кадров стека. Каждый кадр стека представляет собой вызов функции. Самый верхний кадр стека представляет собой последний.

Переполнение стека

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

Вызовите указанную выше функцию с очень большим числом. Скажите сто тысяч.

let factorial = fact 100000

И вот так вы переполняете стек.

Рекурсия хвоста

Хвостовая рекурсия - это рекурсия функции, которая не потребляет пространство стека и, следовательно, предотвращает переполнение стека. Если рекурсивная функция сделана хвостовой рекурсивной, то она более эффективна, чем не хвостовая рекурсивная функция, потому что каждый вызов функции не должен идти в стек и всплывать после завершения вызова. И это предотвращает некрасивое переполнение стека.

Давайте создадим рекурсивную функцию, чтобы найти сумму целых чисел от 1 до заданного n. Это будет параметр функции. Базовый случай, когда рекурсия останавливается, - это когда n равно нулю. Вот функция

let rec sumOfIntegers n =
 if n = 0 then 0
 else
  n + sumOfIntegers (n-1)

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

let sumOfIntegersTr n =
 let rec sumrec n sum =
  if n<= 0 then sum
  else
   sumrec (n-1) (n+sum)
 sumrec n 0

Функция sumOfIntegersTr принимает n в качестве аргумента. Обратите внимание, что это не рекурсивная функция. Он определяет вложенную функцию sumrec, которая является рекурсивной. Сразу после определения sumrec вызывается sumrec.

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

sumrec принимает 2 аргумента. n, очевидное число и сумма, которые он использует для накопления суммы числа. Первый вызов sumrec выполняется внешней функцией sumOfIntegersTr. Он вызывается с n и 0, 0 - начальное значение для sum. Таким образом, выполняется добавление аргумента к вызову функции. Базовый вариант возвращает накопленную сумму. Довольно аккуратно. Выполните отладку и посмотрите на стек вызовов для проверки.

Теперь давайте сделаем эту факториальную функцию хвостовой рекурсивной. Помните, что последнее выражение рекурсивного случая должно быть просто вызовом функции. Я также буду использовать аккумулятор с именем factorial для хранения значения факториала. Так же, как sum в sumrec.

let factTr n =
 let rec factRec n factorial =
  if n <= 1I then factorial
  else
   factRec (n-1I) (n*factorial)
 factRec n 1I

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

Надеюсь, вам понравилось это читать. До скорого. Ваше здоровье.

Если вам нравится мой контент, дайте мне подписаться на меня

Средний - https://vijeshsalian.medium.com/

Twitter - https://twitter.com/vijeshsalian

LinkedIn - https://www.linkedin.com/in/vijeshsalian/