Вступ
Хвостова рекурсія
Функція вважається хвостово-рекурсивною, якщо останнє, що вона виконує, - це виклик самої себе.
Щоразу, коли викликається будь-яка функція, кадр стека з її локальними змінними та аргументами кладеться на вершину стека викликів функцій.
Коли функція повертає результат, кадр стека видаляється зі стека.
Хвостово-рекурсивні функції дозволяють застосувати оптимізацію хвостових викликів (або усунення хвостових викликів).
Це оптимізація, яка дозволяє наступному викликові функції повторно використати останній кадр стека, коли попередня функція вже точно не потребуватиме його.
Це знімає занепокоєння щодо переповнення стека викликів функцій, тобто ситуації, коли кадрів у стеку так багато, що не залишається памʼяті, щоб створити ще один.
Оптимізація хвостових викликів у Elm
За певних умов компілятор Elm здатен автоматично виконувати оптимізацію хвостових викликів під час компіляції в JavaScript.
Оптимізація стає можливою для рекурсивної функції, коли остання операція в гілці полягає у виклику самої функції в простому застосуванні функції.
Розгляньмо кілька прикладів:
factorial : Int -> Int
factorial n =
if n <= 1 then
n
else
n * factorial (n-1)
Наведена вище реалізація не є хвостово-рекурсивною, бо остання операція в гілці else - це множення n *.
factorial : Int -> Int
factorial n =
factorialHelper n n
factorialHelper : Int -> Int -> Int
factorialHelper n resultSoFar =
if n <= 1 then
resultSoFar
else
factorialHelper (n-1) (n * resultSoFar)
Наведена вище реалізація хвостово-рекурсивна, і її буде оптимізовано, бо остання операція в гілці else - це виклик factorialHelper самої себе.
Це було б неможливо для функції з сигнатурою типу Int -> Int, тож на практиці оптимізації хвостових викликів часто досягають, визначаючи допоміжні функції.
Вказівки
Piper — завзята пекарка пирогів.
Ніхто не знає, чи взялася вона пекти пироги через своє імʼя, чи змінила імʼя, щоб воно пасувало до її захоплення.
На перший погляд, друге здається малоймовірним, але ж Piper просто небайдужа до пирогів.
Вона постійно щось мудрує на кухні, доопрацьовує рецепти, вдосконалює свою майстерність, на превелику радість своїх друзів.
А що зацікавило її останнім часом?
Пекти пироги якомога круглішими, аж до математичної досконалості, за допомогою її улюбленого числа, яке, як неважко здогадатися, є π.
Piper знайшла чудову формулу, щоб обчислювати π ітеративно: перетворення збіжності Ньютона-Ейлера:
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
Допоможіть Piper спекти її математично досконалий пиріг, обчисливши π.
1. Факторіал
Для початку трохи розімнімося.
Оператор факторіала, який зазвичай записують як !, визначають так:
0! = 1
n! = 1 * 2 * 3 * ... * n
Визначте функцію factorial, яка обчислюватиме факторіал за допомогою хвостової рекурсії.
factorial 4
-- 24
2. Подвійний факторіал
Оператор подвійного факторіала, який зазвичай записують як !!, визначають так:
0!! = 1
n!! = 1 * 3 * 5 * ... * n (for odd n)
n!! = 2 * 4 * 6 * ... * n (for even n)
Визначте функцію doubleFactorial, яка обчислюватиме факторіал за допомогою хвостової рекурсії.
factorial 5
-- 15
factorial 6
-- 48
3. Перетворення збіжності Ньютона-Ейлера
Визначте функцію pipersPi, яка наближатиме π, використовуючи задану кількість членів формули перетворення збіжності Ньютона-Ейлера, за допомогою хвостової рекурсії.
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
Обчислімо перший член разом.
Якщо взяти верхню межу 0 (замість нескінченності), отримаємо:
π / 2 ≈ Sum for k from 0 to 0 of ( k! ) / ( 2 * k + 1 )!!
π / 2 ≈ ( 0! ) / ( 2 * 0 + 1 )!!
π / 2 ≈ 0! / 0!!
π / 2 ≈ 1 / 1
π / 2 ≈ 1
π ≈ 2
Кожен додатковий член покращуватиме наближення.
pipersPi 0
-- 2.0
pipersPi 1
-- 2.6666666
Навчальна вправа
