Рекурсія
Функція називається рекурсивною, якщо вона викликає саму себе.
Одна з ключових відмінностей між викликом функції та циклом полягає в тому, що виклик функції кладе на стек адресу, на яку потрібно повернутися.
Це означає, що рекурсивна функція зазвичай потребує більше місця на стеку, ніж еквівалентний цикл.
Як наслідок, функція, яка раз за разом викликає саму себе, може зрештою вичерпати весь стек.
Це називається переповненням стека.
Саме тому кожна рекурсивна функція повинна мати принаймні один базовий випадок, тобто ситуацію, коли функція повертає результат, не викликаючи себе.
Будь-який рекурсивний виклик рано чи пізно має дійти до базового випадку.
Наприклад, функцію факторіала n! = n * (n - 1) * ... * 1 можна визначити рекурсивно, взявши 1 за базовий випадок:
factorial:
; the argument `n` is passed on `rdi`
; the factorial will be returned on `rax`
cmp rdi, 1
jle .base_case ; base case -> if rdi <= 1, return 1
push rdi ; save n
dec rdi ; rdi = n - 1
call factorial ; recursive call, rax = (n - 1)!
pop rdi ; restore n
imul rax, rdi ; rax = n * (n - 1)! = n!
ret
.base_case:
mov rax, 1
ret
Зауважмо, що factorial має виконати push rdi перед рекурсивним викликом і pop rdi після нього.
Це тому, що після повернення з рекурсивного виклику їй усе ще потрібне n, щоб обчислити n * (n-1)!.
Зауважмо також, що використання регістра, який має зберегти викликана функція, цієї проблеми не розвʼязало б.
Навіть попри те, що рекурсивна функція потенційно може викликати саму себе, вона сама є викликаною функцією для якоїсь іншої.
Це означає, що функція також повинна зберегти регістри, які має зберегти викликана функція, перш ніж скористатися ними, і відновити їхні значення після використання.
Зазвичай це роблять послідовністю push/pop, як ми бачили в попередній концепції.
Оскільки кожен кадр рекурсивної функції, за винятком базового випадку, теж є викликачем, який має зберегти власні локальні змінні, цю послідовність push/pop доводиться повторювати для кожного кадру.
Навіть збереження змінної безпосередньо на стеку, без використання регістрів, усе одно коштувало б ті самі 8 байтів на кадр.
Це означає, що кожен рекурсивний виклик додає до стеку 8 байтів під адресу повернення, яку кладе call, плюс 8 байтів на кожну локальну змінну, яку потрібно зберегти.
Функція додаватиме ці байти до стеку з кожним кадром, аж поки не дійде до базового випадку.
І лише тоді вона почне розгортатися у зворотному порядку: кожен рекурсивний виклик виконає стільки pop, скільки потрібно, а потім ret.
Наприклад, якби factorial викликали з аргументом 10, вона викликала б себе девʼять разів, перш ніж дійти до базового випадку 1.
На той момент 144 байти були б використані на збереження n (8 байтів) та адреси повернення (8 байтів) для кожного попереднього кадру.
Хвостовий виклик
У деяких ситуаціях функція не виконує більше жодної роботи після виклику іншої функції та перед поверненням.
Розгляньмо, наприклад:
times_three:
imul rax, rdi, 3
ret
triple_of_square:
imul rdi, rdi
call times_three
ret
Функція triple_of_square:
- множить переданий аргумент (у
rdi) сам на себе, отримуючи його квадрат;
- потім викликає
times_three, яка повертає три, помножені на переданий аргумент.
У результаті triple_of_square повертає 3*x², де x позначає її аргумент, переданий у rdi.
Зауважмо, що після виклику times_three у triple_of_square не виконується жодної роботи: функція просто повертає керування.
У такій ситуації замість call функція може використати jmp і передати керування викликаній функції:
times_three:
imul rax, rdi, 3
ret
triple_of_square:
imul rdi, rdi
jmp times_three
Це називається хвостовим викликом.
Основна перевага хвостового виклику полягає в тому, що ми оминаємо додаткові витрати на call.
call кладе на стек адресу повернення, і щоб керування повернулося до того місця, потрібен відповідний ret.
Хвостовий виклик оминає і те, і те: немає адреси повернення, яку треба класти на стек, і немає зайвого ret, з яким її потрібно було б зіставити, а є лише власний ret викликаної функції.
Хвостова рекурсія
Хвостовий виклик особливо корисний для рекурсивних функцій, які можуть викликати себе багато разів, перш ніж повернути результат.
Однак не кожен рекурсивний виклик можна безпосередньо перетворити на хвостовий.
Оскільки jmp передає керування викликаній функції, викликач не може виконати жодної роботи після хвостового виклику.
Наприклад, розглянута раніше функція factorial не є хвостово-рекурсивною.
Після рекурсивного виклику їй усе ще потрібно помножити результат на поточне n за допомогою imul rax, rdi.
У таких ситуаціях іноді можна скористатися акумулятором, який збиратиме проміжні обчислення і буде повернутий у кінці.
Наприклад, ми можемо визначити factorial_helper, яка виконує більшу частину роботи, а потім factorial задає початкове значення акумулятора й передає керування factorial_helper:
factorial_helper:
; the argument `n` is passed on `rdi`
; `rax` is used as an accumulator and will be returned at the end
cmp rdi, 1
jle .base_case
imul rax, rdi ; we accumulate the partial result on `rax`
dec rdi ; rdi = n - 1
jmp factorial_helper ; tail call to accumulate (n - 1)!
.base_case:
ret ; returns the factorial already accumulated on `rax`
factorial:
mov rax, 1 ; initial value for the accumulator
jmp factorial_helper ; tail call
Оскільки після рекурсивного виклику більше нічого не виконується, нам більше не потрібно зберігати rdi.
Тут немає ні call, ні push rdi, тож кожна рекурсивна ітерація додає до стеку 0 байтів: додаткове місце на стеку не витрачається.
Ця версія витримує як завгодно велике n, не переповнюючи стек.
Вона і ефективніша, і безпечніша.
У деяких випадках, змінивши порядок функцій, можна взагалі уникнути навіть jmp до допоміжної функції.
Наприклад, factorial і triple_of_square можна переписати так:
factorial:
mov rax, 1
factorial_helper:
cmp rdi, 1
jle .base_case
imul rax, rdi
dec rdi
jmp factorial_helper
.base_case:
ret
triple_of_square:
imul rdi, rdi
times_three:
imul rax, rdi, 3
ret
У наведеному фрагменті виконання factorial переходить далі, у factorial_helper.
Те саме відбувається з triple_of_square і times_three.
В обох випадках виконання продовжується послідовно, і здається, ніби хвостова функція - це просто локальна мітка всередині «головної» функції.
Насправді між будь-якою локальною міткою та функцією немає жодної принципової різниці.
Асемблер x86-64 не надає жодному з них особливого статусу: усе це просто адреси в секції з виконуваним кодом, наприклад у section .text.
Отже, хвостово-рекурсивну функцію можна уявляти собі фактично так само, як цикл, де рекурсивний виклик стрибає назад на початок, а базовий випадок - це умова, яка завершує цикл.
Навчальна вправа
