Recursive function in assembly in ARM Architecture - Step-by-Step Execution

Concept Flow - Recursive function in assembly

Call recursive function

↓

Check base case?

Yes→Return base value

No↓

Save current state (push registers)

↓

Prepare arguments for recursive call

↓

Call recursive function again

↓

Receive return value

↓

Restore state (pop registers)

↓

Compute result

↓

Return result

↓

End

The recursive function calls itself after checking a base case, saving state before the call and restoring it after, then returns the computed result.

Execution Sample

ARM Architecture

factorial:
  CMP r0, #1
  BLE end_factorial
  PUSH {r0, lr}
  SUB r0, r0, #1
  BL factorial
  POP {r1, lr}
  MUL r0, r0, r1
end_factorial:
  BX lr

This ARM assembly code computes factorial recursively by calling itself with decremented argument until base case.

Analysis Table

Step	Instruction	Register r0 (n)	Action	Stack (LR) State	Return Value
1	CMP r0, #1	3	Check if n <= 1	Empty	N/A
2	BLE end_factorial	3	No branch, n > 1	Empty	N/A
3	PUSH {r0, lr}	3	Save return address and n	LR pushed	N/A
4	SUB r0, r0, #1	2	Decrement n	LR pushed	N/A
5	BL factorial	2	Recursive call with n=2	LR pushed	N/A
6	CMP r0, #1	2	Check if n <= 1	LR pushed	N/A
7	BLE end_factorial	2	No branch, n > 1	LR pushed	N/A
8	PUSH {r0, lr}	2	Save return address and n	LR pushed twice	N/A
9	SUB r0, r0, #1	1	Decrement n	LR pushed twice	N/A
10	BL factorial	1	Recursive call with n=1	LR pushed twice	N/A
11	CMP r0, #1	1	Check if n <= 1	LR pushed twice	N/A
12	BLE end_factorial	1	Branch taken, base case	LR pushed twice	N/A
13	BX lr	1	Return from base case	LR pushed twice	Return 1
14	POP {r1, lr}	1	Restore saved n and return address	LR pushed once	Return 1
15	MUL r0, r0, r1	2	Multiply n * factorial(n-1)	LR pushed once	Return 2
16	BX lr	2	Return from recursion level	LR pushed once	Return 2
17	POP {r1, lr}	2	Restore saved n and return address	Empty	Return 2
18	MUL r0, r0, r1	6	Multiply n * factorial(n-1)	Empty	Return 6
19	BX lr	6	Return from initial call	Empty	Return 6
20	-	-	-	-	Execution ends, factorial(3) = 6

💡 Execution stops after returning from the initial call with factorial(3) computed as 6.

State Tracker

Variable	Start	After Step 4	After Step 9	After Step 13	After Step 15	After Step 18	Final
r0 (n)	3	2	1	1	2	6	6
Stack LR	Empty	LR pushed	LR pushed twice	LR pushed twice	LR pushed once	Empty	Empty
Return Value	N/A	N/A	N/A	1	2	6	6

Key Insights - 3 Insights

Why do we push and pop the LR register during recursion?

Because each recursive call needs to remember where to return after finishing. Pushing LR saves the return address before the call (see steps 3 and 8), and popping restores it after the call (steps 14 and 17).

How does the function know when to stop calling itself?

It checks if the input n is less than or equal to 1 (step 1 and 11). If yes, it returns immediately without further recursion (step 12). This is the base case.

Why do we decrement r0 before the recursive call?

Because factorial(n) calls factorial(n-1). The SUB instruction (steps 4 and 9) prepares the argument for the next recursive call.

Visual Quiz - 3 Questions

Look at the execution table at step 9, what is the value of r0?

A 3

B 2

C 1

D 0

💡 Hint

Check the 'Register r0 (n)' column at step 9 in the execution_table.

At which step does the base case condition become true and recursion stops?

A Step 6

B Step 12

C Step 18

D Step 3

💡 Hint

Look for the step where BLE branch is taken indicating n <= 1.

If we did not push LR before the recursive call, what would happen?

A The return address would be lost, causing incorrect return.

B The base case would never be reached.

C The function would return correctly.

D The stack would overflow.

💡 Hint

Refer to key_moments about why LR is pushed and popped during recursion.

Concept Snapshot

Recursive function in ARM assembly:
- Check base case with CMP and branch
- Save LR (return address) with PUSH before recursive call
- Decrement argument (r0) before calling recursively
- After recursive call, restore LR with POP
- Compute result (e.g., multiply for factorial)
- Return with BX lr
Base case stops recursion to avoid infinite calls.

Full Transcript

This visual execution trace shows how a recursive function works in ARM assembly. The function first compares the input value in register r0 to 1 to check the base case. If the value is less or equal, it returns immediately. Otherwise, it saves the return address by pushing the LR register onto the stack. Then it decrements r0 by 1 and calls itself recursively. After the recursive call returns, it restores LR by popping from the stack, multiplies the returned value by the current n, and returns the result. The stack keeps track of return addresses for each recursive call. This process repeats until the base case is reached, then the calls return one by one, computing the factorial. The execution table tracks each step, register values, stack state, and return values to help visualize the recursion flow.