How does recursive return value encoding work (e.g., binary search path)?

Each level shifts in one bit: going left returns 2*result, going right returns 2*result+1, and the found base case returns 0 — so the return value's bits spell out the path.

* Return-value bit encoding: left = 2r (bit 0), right = 2r+1 (bit 1), base = 0. *

# Left branch (target is smaller)
call <func4>
add  %eax, %eax
# return 2 * result

# Right branch (target is larger)
call <func4>
lea  0x1(%rax,%rax,1), %eax
# return 2 * result + 1

# Base case (found)
mov  $0x0, %eax
# return 0

Decoding a return value:

• Return value 7 = binary 111 = right, right, right
• Return value 6 = binary 110 = right, right, left
• Return value 0 = found immediately (no recursion needed)

To find the input that produces a target return value: Trace the binary representation. Each 1 bit means "go right", each 0 means "go left". Read from most significant bit to least significant.

Go deeper:

• Recursion (computer science) - base case vs recursive case and how each step approaches termination
• Binary search tree - how left/right comparisons at each node encode a path down the tree