Introduction
Recursion is a common topic during coding interview. This post talks about how to succesfully write a correct recursion solution for a coding exercise.
Method signature
Method signature we care in a recursion method is defined by all the inputs(including types and orders) taken by the method, and outputs we expect from the method call. Before we write a curcusion method, we need to carefully think about the method signature. For the input, we need to list out all the necessary parameters and also trying to remove the unnecessary/duplicated parameters. For the output, we need to think about what info the caller is expected from this method.
Problem size break down
We need to break down the size of the problem efficiently, otherwise it’s easy leading to stack overflow. There can be multiple ways to break down the problems size, depending on the question. Let’s say the input is an array, and start end end indices indicating the candidates range. We can either shink the array by splicing a subarray of from it, or we can narrow down the size between the boundary indices. No matter which way we choose, we need to break down the problem size efficiently.
Exit condition
The recursion call cannot be lasted forever due to the stack call height limit, thus we must clearly define the exit condition, which acting as our “base case”. Once the recursion call is reaching at “base case”, we no longer keep recusioning and start to return the value back along the call stack.
Consolusion
We have talked about 3 key points for successfully writing a recursion algorithm to solve the coding exercise: defind method signature, problem size break down and exit condition. Again, we need to practice. Practice makes better coding skills.