I find the easiest way to get past the abstraction of recursion is to describe what a function actually is, rather than the handwavey definitions we usually steal from math. A function is a stack and a list of instructions. When you call a function, you add things to the stack, and when you return from the function, you throw those things away.
Stack of papers, flight of stairs, layers of onions, circle of life, etc. they all just harken back to what it actually is without having to define it directly.
If we're using an 80x86 processor, the function concept is more or less implemented by several facilities - you have a sequence of instructions somewhere in memory, you have a stack area (shared by everything in a given address-space, using a stack pointer in the cpu), you a call instruction that pushes the current instruction pointer to the stack as well as pushing flags and similar stuff to the stack and you have the return instruction, which does the opposite, restore instruction pointer and whatever else was pushed in the call.
Which is to say that on a raw, low level, functions don't "exist" in the fashion a programmer imagine at a higher level. That's not saying the concept is wrong but is saying that the people don't easily see functions as the natural building blocks of everything might be wrong either.
Stack of papers, flight of stairs, layers of onions, circle of life, etc. they all just harken back to what it actually is without having to define it directly.