How Does This Recursion Work

How does recursion work?

Here's a simple example of recursive method: -

public int recur(int count) {
   if (count < 10) {
       return count + recur(count++);
   }
   return count;
}

System.out.println(recur(0));  // Invoke first time

How do compilers understand recursion?

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.

How does this recursion work when deep clone?

You should think of this as a tree data structure problem, one object has x child properties, each child property has x more child properties, and so on... For every child, there's a specific subtree that this child generates, so you can recursively call this function for every child since every child has its own tree of properties. For more understanding of this type of algorithm, you should look into Trees.

---

Related Topics