Recursive function in assembly in ARM Architecture

Introduction

Recursion lets a function call itself to solve smaller parts of a problem. In assembly, it helps break down complex tasks step-by-step.

Calculating factorial of a number where the problem breaks down into smaller factorials

Traversing tree-like data structures where each node leads to smaller subtrees

Solving problems like Fibonacci numbers where each result depends on previous results

Implementing algorithms like quicksort or mergesort that divide data into smaller parts

When a problem naturally fits a divide-and-conquer approach requiring repeated function calls

Core Concept

ARM Architecture

/* ARM Assembly Recursive Function Template */

.global recursive_function
recursive_function:
    push {lr}              /* Save return address */

    /* Base case check */
    cmp r0, #0             /* Compare input parameter in r0 with 0 */
    beq base_case          /* If zero, jump to base case */

    /* Recursive case */
    sub r0, r0, #1         /* Decrement parameter */
    bl recursive_function  /* Recursive call */

    /* Process after recursive call */
    /* ... your code ... */

    pop {pc}               /* Return from function */

base_case:
    /* Base case code here */
    mov r0, #1             /* Example: return 1 */
    pop {pc}               /* Return from function */

The function uses push {lr} to save the return address before calling itself.

The base case stops the recursion to avoid infinite calls.

Key Points

This example shows a factorial function using recursion. It saves the return address, checks the base case, calls itself with n-1, then multiplies the result.

ARM Architecture

/* Example: Factorial function in ARM assembly */

.global factorial
factorial:
    push {lr}              /* Save return address */
    cmp r0, #0             /* Check if n == 0 */
    beq factorial_base     /* If yes, base case */

    sub r0, r0, #1         /* n = n - 1 */
    bl factorial           /* Recursive call factorial(n-1) */

    mul r0, r0, r1         /* Multiply result by n (stored in r1) */
    pop {pc}               /* Return */

factorial_base:
    mov r0, #1             /* factorial(0) = 1 */
    pop {pc}               /* Return */

This shows handling the edge case where the input is zero, immediately returning a value without further recursion.

ARM Architecture

/* Edge case: Recursive call with parameter 0 */

.global test_zero

test_zero:
    push {lr}
    cmp r0, #0
    beq base_case
    /* Recursive call if not zero */
    sub r0, r0, #1
    bl test_zero
    pop {pc}

base_case:
    mov r0, #42  /* Return a fixed value for base case */
    pop {pc}

This example handles the case when the input is 1, stopping recursion and returning a value.

ARM Architecture

/* Edge case: Recursive call with parameter 1 (single element) */

.global test_one

test_one:
    push {lr}
    cmp r0, #1
    beq base_case
    sub r0, r0, #1
    bl test_one
    pop {pc}

base_case:
    mov r0, #100  /* Return a fixed value for base case */
    pop {pc}

This example shows recursion stopping at both the start (0) and end (10) of a sequence.

ARM Architecture

/* Edge case: Recursive call at the beginning and end of a sequence */

.global recursive_sequence

recursive_sequence:
    push {lr}
    cmp r0, #0
    beq base_case
    cmp r0, #10
    beq end_case

    sub r0, r0, #1
    bl recursive_sequence
    pop {pc}

base_case:
    mov r0, #0
    pop {pc}

end_case:
    mov r0, #10
    pop {pc}

Detailed Explanation

This program calculates factorial of 5 using recursion. It saves the return address, checks the base case (0), calls itself with n-1, then multiplies the result by n. The final result 120 is stored in register r0.

ARM Architecture

/* Complete ARM Assembly Program: Recursive Factorial Function */

.global main

/* factorial function: calculates factorial of r0 */
factorial:
    push {lr}              /* Save return address */
    cmp r0, #0             /* Check if n == 0 */
    beq factorial_base     /* Base case: factorial(0) = 1 */

    /* Save current n in r1 before recursive call */
    mov r1, r0
    sub r0, r0, #1         /* n = n - 1 */
    bl factorial           /* Recursive call factorial(n-1) */

    mul r0, r0, r1         /* Multiply result by n */
    pop {pc}               /* Return */

factorial_base:
    mov r0, #1             /* Return 1 for factorial(0) */
    pop {pc}

/* main function to test factorial */
main:
    mov r0, #5             /* Calculate factorial(5) */
    bl factorial           /* Call factorial */

    /* Result in r0 now contains 120 */
    /* Normally, here you would return or use the result */

    /* Infinite loop to end program (for embedded) */
end:
    b end

Important Notes

Time complexity of recursive factorial is O(n) because it calls itself n times.

Space complexity is O(n) due to call stack growth with each recursive call.

Common mistake: forgetting to save and restore the return address (lr) causes crashes.

Use recursion when problems naturally break down into smaller similar problems; otherwise, iteration may be simpler and more efficient.

Summary

Recursive functions call themselves to solve smaller parts of a problem.

In ARM assembly, save the return address with push {lr} before recursion and restore it with pop {pc} to return.

Always include a base case to stop recursion and avoid infinite loops.

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