When I was in school learning about recursion for the first time, I only truly 'got' it when I opened up Excel and drew it out like this: fib(5) n=5 --------

When I was in school learning about recursion for the first time, I only truly 'got' it when I opened up Excel and drew it out like this: fib(5) n=5 ---------------- | n=5 |-- fib(5-1=4) ------------ |-- | n=4 |-- | -- fib(4-1=3) ------- |-- | -- | n=3 |-- | -- | ... |-- | -- end of fib(3) ---- |-- | here n is still 4 |-- end of fib(4) | here n is still 5 |-- fib(5-2=3) ------------ |-- | n=3 |-- | ... |-- end of fib(3) | here n is still 5 end of fib(5) with different colours for each invocation. The point I'd been missing/not taught very well is that each invocation has its own values for the arguments, and once that invocation returns, the previous invocation still has whatever values it used to have for the arguments. That was the key for me of 20 years ago, and the Excel visualisation was when the penny dropped.