= Solution
The blanks are \b[`x < 2`] and \b[`return x - foo(x + 1)`]. The compiled `slti` and `bne` select the first branch exactly for $x<2$. Otherwise `addi` forms $x+1$, `jal foo` returns its value in `$v0`, and `sub $v0, $s0, $v0` subtracts that value from the preserved $x$. Thus the complete high-level implementation is
``
proc bar(val x : int) : int
begin if x < 2 then
return 1
else
return x - foo(x + 1)
end
end
``
Although the immediate call increases the argument, substitution into `foo`'s two recursive calls decreases the corresponding `bar` arguments to $x-1$ and $x-2$ whenever the recursive branch is entered. The mutual <recursion> therefore terminates on ordinary integer inputs, assuming sufficient <stack> space and no machine arithmetic overflow.
Back to article page
