How do you recognize a recursive function in assembly?

Look for a function that calls its own label, after modifying its arguments and with a conditional base case that returns without recursing.

* A function that calls its own label. Spot the base case (conditional return of a constant), argument modification before the self-call, and result combination after it returns. *

func4:
    # base case check
    cmp  %edi, %eax
    je   .L_base_case

    # modify arguments
    lea  -0x1(%rax), %edx
    # recursive call to self
    call <func4>

    # combine result
    add  %eax, %eax
    ...

.L_base_case:
    mov  $0x0, %eax
    ret

Identifying elements:

1. Base case: A conditional jump that skips the recursive call and returns a constant
2. Argument modification: Registers changed before the self-call (e.g., narrowing a range)
3. Result combination: Arithmetic on %eax after the call returns (e.g., 2 * result, 2 * result + 1)

Common recursive patterns in bomb labs:

• Binary search: left/right branching with 2*result / 2*result+1
• Tree traversal: two possible recursive paths
• Factorial-like: multiply result by some value

Go deeper:

• Recursion in computer science (Wikipedia) — Defines base case and recursive call, the two structural elements you look for in the disassembly.
• Call stack (Wikipedia) — Recursion relies on each self-call pushing its own return address/frame; explains why the stack grows per level.