How do compilers understand recursion?

Question

I've delt with recursion when programming in c and python and I'm guessing it's used in many other languages as well, but how does a compiler actually interpret a recursion function? How can it use the function in it's own definition?

Answer 1

but how does a compiler actually interpret a recursion function? How can it use the function in it's own definition?

To understand this you just need to under stand how a compiler interpret a function. For C, the function is just a symbol, or a pointer pointing to the entry address in memory. Intuitively but not strictly, the function call would be compile to such assemble instruction:

CALL address_of_function

See? The compiler does not need to know whether the function is recursive or not. It just make CPU jump to the address of function entry and keep on executing instructions.

And that's why we can use that function even if its definition is not finished. The compiler just need to know a start address, or a symbol, and then it would know where to jump. The body of the function could be generated later.

However, you might want to know the Tail Recursion, that is a special case commonly in functional programming languages. The "tail recursion" means the recursive function call is the last statement in function definition. As @paulsm4 mentioned, when calling a function, the compiler need to push context and parameters into stack, and then recover the context and get return values from it. Thus, if your function calls itself and then itself ..., the stack would be too deep until the memory runs out. But if the function call is the last statement in function definition, then there would be no necessary to save context in the stack, and we can just overwrite it. Thus, the stack would not overflow even if the function calls itself infinitely.

Answer 2

It's entirely compiler-dependent ... but most compilers in most languages implement recursion by using the stack.

The compiler generates the code that pushes the program arguments, saves the current stack and frame pointers, then simply calls the same function (with the newly updated stack).

Here is a very good article: Understanding the stack