> (1) whether a function is said to have worked or not could be dependent on a call multiple levels deep from the original call, (2) the immutable constant named `foo` you created within the function body might contain different values at every deeper call (therefore it is no longer an effective name to refer to 'one thing'),

These aren't issues as long as you can prove your recurrence relation is correct. If you treat the recursive call as a black box, there is no reason to think about how it actually behaves and computes its result.