Recursive function in assembly in ARM Architecture - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define the base case check in a recursive factorial function.

ARM Architecture

cmp r0, [1]
beq end_factorial

Drag options to blanks, or click blank then click option'

A#1

B#0

Cr1

Dr2

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with 1 instead of 0 for the base case.

Using a register instead of an immediate value in the compare instruction.

The base case for factorial is when the input is 0, so the function returns 1. The comparison should be with 0.

2fill in blank

medium

Complete the code to decrement the argument register before the recursive call.

ARM Architecture

sub r0, r0, [1]

Drag options to blanks, or click blank then click option'

A#1

Br1

Cr2

D#0

Attempts:

3 left

💡 Hint

Common Mistakes

Subtracting 0 or a register instead of 1.

Using the wrong register as the source or destination.

To compute factorial recursively, the argument must be decremented by 1 before the recursive call.

3fill in blank

hard

Fix the error in the recursive call instruction to correctly branch to the factorial function.

ARM Architecture

bl [1]

Drag options to blanks, or click blank then click option'

Afactorial

Bfactor

Cfact

Dfact_recursive

Attempts:

3 left

💡 Hint

Common Mistakes

Using an incorrect or partial label name for the branch.

Misspelling the function label.

The label for the factorial function is 'factorial', so the branch with link instruction must call 'factorial'.

4fill in blank

hard

Fill both blanks to multiply the current argument with the result of the recursive call.

ARM Architecture

mul r0, r0, [1]
mov [2], r0

Drag options to blanks, or click blank then click option'

Ar1

Br0

Cr2

Dr3

Attempts:

3 left

💡 Hint

Common Mistakes

Multiplying by the wrong register.

Moving the result to the wrong register.

After the recursive call, the result is in r0. Multiply r0 by the current argument (saved in r1). Then move the result back to r1 for further use.

5fill in blank

hard

Fill all three blanks to correctly save and restore the link register around the recursive call.

ARM Architecture

push [1]
bl factorial
pop [2]
mov [3], r0

Drag options to blanks, or click blank then click option'

A{lr}

Cr1

Dr0

Attempts:

3 left

💡 Hint

Common Mistakes

Not saving or restoring the link register.

Using the wrong registers in push/pop instructions.

Before the recursive call, save the link register (lr) on the stack with push. After the call, restore it with pop. Finally, move the result from r0 to the desired register.

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