I think the best way to understand recursion is in terms of induction. If someone gave you the solution to your problem for different inputs, could you compose

I think the best way to understand recursion is in terms of induction. If someone gave you the solution to your problem for different inputs, could you compose them together to solve the problem for your current input? Then you just have to show termination. Thinking procedurally (i.e. in terms of 'unfolding' the call stack) is unlikely to provide much insight.