Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

assembly

What is recursion in assembly language?

Rukhshan Haroon

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Recursion is a unique way of implementing a function and is commonly used in high-level programming languages. A recursive function typically calls itself within itself and returns only when the base case- a special condition- is met.

The time and space complexity of recursive functions may be greater than usual functions in some cases. However, recursive functions are typically much shorter in size.

In assembly language, we can implement recursive functions using procedures.

Multiple procedures can be defined in the text segment. Unless the base case is met, the same procedure may be called repeatedly. Upon meeting the base case, we can return from the procedure or terminate the program using the exit system call.

Example

The program below recursively prints the digits of an array in reverse order. First, we store an array with six elements alongside its size in a variable in the data segment. Subsequently, we use the print and check procedures to print array elements and check whether or not the base case has been met. If the base case is met, the exit system call is called to terminate the program gracefully.

section .text
global _start
_start:
call check
print:
mov edi, arr ;fetches pointer to array
add edi, [count] ;updates and stores the adress of the array element in edi that is to be printed
mov ecx, [edi] ;gets element in the adress that needs to be printed from the array
add ecx, 48 ;converts number in array to char
push ecx ;pushes to stack as we require an address
mov ecx, esp ;obtains the address of the number converted to char and saves it in ecx
mov edx, 1 ;message length, 1 byte stored in edx
mov ebx, 1 ;file descriptor number for stdout stream stored in ebx
mov eax, 4 ;system call number for the write system call stored in eax
int 0x80 ;kernel interrupt to execute the write system call in kernel mode
dec byte [count] ;decrements count
call check ;calls check
ret
check:
cmp byte [count], -1
jg print
mov eax, 1 ;system call number of the exit system call
int 0x80 ;kernel interrupt to call the exit system call
section .data
arr db 1,2,3,4,5,6
count db 5
section .bss

Upon execution, the program prints the following output:

654321

RELATED TAGS

assembly

CONTRIBUTOR

Rukhshan Haroon
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring