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.

Practice

1. What is the main purpose of a recursive function in ARM assembly?

easy

A. To execute instructions only once

B. To call itself to solve smaller parts of a problem

C. To avoid using the stack

D. To run faster than iterative loops

Solution

1. Step 1: Understand recursion concept

   A recursive function calls itself to break down a problem into smaller parts.

2. Step 2: Apply to ARM assembly context

   In ARM assembly, recursion is used to solve problems by repeated self-calls with updated parameters.

3. Final Answer:

   To call itself to solve smaller parts of a problem -> Option B

4. Quick Check:

   Recursion means self-calling function [OK]

Hint: Recursion means function calls itself repeatedly [OK]

Common Mistakes:

• Thinking recursion avoids stack usage
• Confusing recursion with iteration
• Assuming recursion always runs faster

2. Which ARM assembly instruction is commonly used to return from a recursive function call?

easy

A. BL

B. MOV

C. BX LR

D. PUSH

Solution

1. Step 1: Identify return instruction

   In ARM assembly, BX LR is used to branch back to the address stored in the link register, effectively returning from a function.

2. Step 2: Confirm usage in recursion

   Recursive functions use BX LR to return after completing each call.

3. Final Answer:

   BX LR -> Option C

4. Quick Check:

   Return uses BX LR instruction [OK]

Hint: Return from function with BX LR instruction [OK]

Common Mistakes:

• Using BL to return instead of call
• Confusing PUSH with return
• Using MOV incorrectly for return

3. Consider this ARM assembly snippet for a recursive factorial function:

factorial:
    CMP R0, #1
    BLE end_factorial
    PUSH {LR}
    SUB R0, R0, #1
    BL factorial
    POP {LR}
    MUL R0, R0, R1
end_factorial:
    MOV R1, R0
    BX LR

What will be the value in R1 after calling factorial with R0 = 3?

medium

A. 0

B. 3

C. 1

D. 6

Solution

1. Step 1: Trace the recursive factorial

   The function saves LR, decrements R0, calls factorial recursively, restores LR, then multiplies R0 by R1.

2. Step 2: Calculate factorial for R0=3

   Call factorial(3): R0=3, not base case, PUSH LR, SUB R0=2, BL factorial(2). factorial(2): PUSH LR, SUB R0=1, BL factorial(1). factorial(1): base case, sets R1=1, returns. factorial(2): POP LR, MUL R0=1 * R1=1 =1, MOV R1=1, return. factorial(3): POP LR, MUL R0=2 * R1=1=2, MOV R1=2, return.

3. Step 3: Correction

   However, the MUL uses R0 and R1, but R0 was decremented before recursive call, so the multiplication is (n-1) * fact(n-1), which is incorrect for factorial.

4. Step 4: Final value

   Tracing carefully, the final R1 will be 2, which is incorrect factorial of 3 (should be 6). But the code as given will produce 2.

5. Final Answer:

   2 -> Option D

Hint: SUB decrements R0 before call; MUL uses decremented R0 causing incorrect factorial [Check carefully]

Common Mistakes:

• Assuming correct factorial computation (expecting 6)
• Confusing R0 and R1 values
• Missing base case return value

4. Identify the error in this recursive ARM assembly function snippet:

factorial:
    CMP R0, #1
    BLE end_factorial
    SUB R0, R0, #1
    BL factorial
    MUL R0, R0, R1
end_factorial:
    MOV R1, R0
    BX LR

What is the main problem?

medium

A. Missing PUSH and POP of LR causing return address loss

B. Incorrect base case comparison

C. Wrong multiplication order

D. Using MOV instead of MOVS

Solution

1. Step 1: Check stack usage for recursion

   Recursive calls must save LR on stack before calling to preserve return address.

2. Step 2: Identify missing PUSH/POP

   This code lacks PUSH {LR} before BL and POP {LR} after, risking corrupted return address.

3. Final Answer:

   Missing PUSH and POP of LR causing return address loss -> Option A

4. Quick Check:

   Save LR on stack in recursion [OK]

Hint: Always save LR on stack before recursive call [OK]

Common Mistakes:

• Ignoring stack save for LR
• Assuming base case is wrong
• Confusing MOV with MOVS

5. You want to write a recursive ARM assembly function to compute the nth Fibonacci number. Which of these is essential to correctly implement recursion here?

hard

A. Handle base cases to stop recursion and save LR on stack before recursive calls

B. Use only registers without stack to speed up recursion

C. Avoid base cases to allow infinite recursion for all n

D. Use unconditional jumps instead of BL for recursive calls

Solution

1. Step 1: Importance of base cases

   Base cases stop recursion to prevent infinite loops, essential for Fibonacci calculation.

2. Step 2: Save LR on stack before recursive calls

   Saving LR preserves return addresses during multiple recursive calls, avoiding crashes.

3. Final Answer:

   Handle base cases to stop recursion and save LR on stack before recursive calls -> Option A

4. Quick Check:

   Base cases + LR save = correct recursion [OK]

Hint: Always include base cases and save LR in recursion [OK]

Common Mistakes:

• Skipping base cases causing infinite recursion
• Not saving LR causing return errors
• Using jumps instead of BL for calls