Язык ассемблера - Рекурсия

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

Принципы рекурсии и стековые фреймы

Суть рекурсии заключается в том, чтокаждый вызов создаёт новый стековый фрейм, сохраняя текущее состояние в стеке.

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

Основы рекурсии	Описание	Реализация на ассемблере
Условие завершения	Предотвращение бесконечной рекурсии	Условная проверка перехода je/jg
Рекурсивный вызов	Функция вызывает себя	инструкция call
Сохранение состояния	Независимое состояние для каждого вызова	Кадр стека (push ebp; mov ebp, esp)
Передача параметров	Разные параметры каждый раз	поместить параметры в стек

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

Рекурсивная реализация факториала

Пример

; Путь к файлу: factorial.asm
; Рекурсивное вычисление факториала: n! = n * (n-1)!

section .data
n dd 5 ; Вычислить 5!
result dd 0
output_msg db 'Результат факториала: '
output_len equ $ - output_msg
newline db 0xA

section .bss
result_str resb 12

section .text
global _start

_start:
; Вызов factorial(5)
push dword [n] ; Поместить параметр n в стек
call factorial
add esp, 4 ; Очистка параметров
; eax = 120 (5!)

mov [result], eax

; Вывести результат
mov eax, 4
mov ebx, 1
mov ecx, output_msg
mov edx, output_len
int 0x80

; Простой вывод числа (только для демонстрации однозначного числа)
mov eax, [result]
; Здесь упрощено
mov ebx, eax
mov eax, 1
int 0x80

; Процедура: factorial(n)
; Вход: [ebp+8] = n
; Выход: eax = n!
factorial:
push ebp ; Сохранить старый кадр стека
mov ebp, esp ; Установить новый кадр стека

mov eax, [ebp + 8] ; Получить параметр n
cmp eax, 1 ; n <= 1 ?
jg recurse ; n > 1, продолжить рекурсию

; Условие завершения: n <= 1, вернуть 1
mov eax, 1
jmp factorial_end

recurse:
; Сохранить текущее n (регистр будет уничтожен рекурсивным вызовом)
push eax ; Сохранить n

; Рекурсивно вызвать factorial(n-1)
dec eax ; n - 1
push eax ; Аргумент: n-1
call factorial ; Рекурсивный вызов
add esp, 4 ; Очистка параметров

; Восстановить n
pop ebx ; ebx = n

; eax = n * factorial(n-1)
mul ebx ; edx:eax = eax * ebx
; Для меньших значений n edx равен 0, и результат полностью находится в eax

factorial_end:
pop ebp ; Восстановить старый стековый кадр
ret

Полный стек вызовов и процесс возврата при рекурсивном вычислении factorial(5):

Ниже приведён процесс вызова в текстовом виде:

factorial(5)
  -> 5 * factorial(4)
       -> 4 * factorial(3)
            -> 3 * factorial(2)
                 -> 2 * factorial(1)
                      -> 1  (终止条件)
                 <- 1 * 2 = 2
            <- 2 * 3 = 6
       <- 6 * 4 = 24
  <- 24 * 5 = 120

Рекурсивная реализация Фибоначчи

Пример

; Путь к файлу: fibonacci.asm
; Рекурсивно вычислить последовательность Фибоначчи: fib(n) = fib(n-1) + fib(n-2)

section .data
n dd 10 ; Вычислить fib(10)

section .text
global _start

_start:
; Вызвать fib(10)
push dword [n]
call fibonacci
add esp, 4
; eax = fib(10) = 55

mov ebx, eax ; Код выхода = 55
mov eax, 1
int 0x80

; Процедура: fibonacci(n)
; Вход: [ebp+8] = n
; Результат: eax = fib(n)
fibonacci:
push ebp
mov ebp, esp

mov eax, [ebp + 8] ; Получить параметр n

; Условие завершения: вернуть n, когда n <= 1
cmp eax, 1
jg fib_recurse ; n > 1, требуется рекурсия
; n <= 1：fib(0)=0, fib(1)=1
jmp fib_end

fib_recurse:
; ★ Примечание: рекурсия имеет две ветви, поэтому стеком нужно управлять осторожно
push ebx ; Сохранить ebx (он будет использоваться для хранения промежуточного результата)

; Вычислить fib(n-1)
mov eax, [ebp + 8]
dec eax ; n - 1
push eax
call fibonacci
add esp, 4
mov ebx, eax ; ebx = fib(n-1) (сохранить результат!)

; Вычислить fib(n-2)
mov eax, [ebp + 8]
sub eax, 2 ; n - 2
push eax
call fibonacci
add esp, 4
; eax = fib(n-2)

; eax = fib(n-1) + fib(n-2)
add eax, ebx ; eax = fib(n-2) + fib(n-1)

pop ebx ; Восстановить ebx

fib_end:
pop ebp
ret

Рекурсивная версия Фибоначчи включает много дублирующих вычислений. fib(10) вызывает fib(9) и fib(8), а fib(8) вызывается дважды... что приводит к сложности по времени O(2^n). В реальной инженерии рекомендуется использовать циклическую итеративную версию.

Итеративная версия Фибоначчи (сравнение)

Пример

; Путь к файлу: fibonacci_iter.asm
; Итеративная версия: более эффективна, без накладных расходов на рекурсию

section .data
n dd 10

section .text
global _start

_start:
mov ecx, [n] ; ecx = n
dec ecx ; Цикл n-1 раз (начиная со 2-го члена)

mov eax, 0 ; fib(0) = 0
mov ebx, 1 ; fib(1) = 1

cmp ecx, 0
jle fib_done ; n <= 1, вернуть напрямую

fib_loop:
mov edx, ebx ; Сохранить старое значение fib(n-1)
add ebx, eax ; ebx = fib(n-1) + fib(n-2)
mov eax, edx ; Обновить fib(n-2)
loop fib_loop

fib_done:
; Для n=10 в итоге ebx = 55
mov eax, 1
mov ebx, ebx ; Возвращаемое значение = fib(n)
int 0x80

Сравнение рекурсии и итерации

Характеристика	Рекурсия	Итерация
Размер кода	Короче, понятная логика	Длиннее, но хорошая производительность
Использование стека	Каждый вызов занимает кадр стека; может произойти переполнение при большой глубине	Фиксированный небольшой объём памяти
Производительность	Имеет накладные расходы на call/ret	Нет накладных расходов на вызов функции
Читаемость	Интуитивно понятно для задач математической индукции	Требуется вручную поддерживать состояние цикла
Применимые сценарии	Обход дерева, алгоритмы «разделяй и властвуй», математическая индукция	Простое повторение, сценарии, чувствительные к производительности

В ассемблере каждый рекурсивный вызов потребляет пространство стека. Размер стека по умолчанию в Linux составляет около 8MB, и рекурсия с глубиной 100000 может вызвать переполнение стека. Как определить, когда использовать рекурсию: когда глубина рекурсии задачи контролируема (например, глубина сбалансированного дерева O(log n)), а рекурсивная логика намного понятнее, чем итерация.

Другие расширения