Some thoughts and tips on recursion
Throughout the years many colleagues and individuals who saught professional advise shared with me their discomfort with coding recursive code.
I would like to defer the discussion whether recursive code should used in your work related code, and focus on the fact that there is a signficiant amount of coding problems which are asked in interviews, that can be solved in an elegant (and even easier) way, if a recursive solution is used.
Usually when one studies the topic of recursion they encounter classic examples, like the Fiboannci or the factorial calculation problems.
Not only these examples are trivial, but they can be implemented in one function.
There are plenty of cases where implemeting with one function is not feasible.
If we look at the reverse singly link linked list problem, the signature of the function is:
When dealing with recursion , one must be in a mindest that the same problem, with a smaller subset of input, or different arguments was already solved, and used the solution to solve the problem.
In this case, one may think that having a reversed list that its head is the second element would solve the problem, but what would be the additonal step?
The function signature, as described above, returns the head of the reversed list. It does not return the second node, which is required to complete the step.
We need to slightly modify the approach, while still keep the function signature that will be used by external callers.
This will be done by introducing a helper function.
The helper function will have a similar signature, and should help to solve the problem while taking into account the constaints of the used data structure.
Our data structure is singly linked linked list. This data structure has reference only to the next nodes in the list.
If we look at linked list of two nodes, reversing is easy.
The head of the reversed list will be head.next, we can set it in our return variable.
We can set the next field of the return variable to point to head.
As the return variable reference to the node referenced by the next field of head, we have a situation where the next fields of both head and toReturn reference the counterpart nodes (there is no reference to null).
We then set the next field of head to reference null.
We can can solve this problem in a slightly different way:
a. We will have a reference to the next element of head.
b. We will set the next field of head to null.
c. We will then set the next field of the refernece introuced at (a) to head
Can we repeat this for every two adjacent nodes?
We can, but prior to the 3rd step we need to make sure that all the remaining nodes were adjusted in the same way.
In addition, the second node will not be referenced by a “toReturn” variable, but will be referenced by a “next” variable, as “toReturn” should be the returned value from the call which is the head of the reversed list.
To alter the reference from the second node to the first, we can clearly see we need references to both these nodes, which we can think of as the current node and the next node.
The stop condition for the helper function is simple, and we can think about it if we think how a list with only one node gets reversed.
Such list will remain the same.
The condition therefore can be:
if next is null return the current element
What values should we pass to the first call?
As mentioned above adjusting the references means that the next field of next should reference current.
The last adjustment should be the one in which next will reference null.
This means that the initial call should be with current equals to null, and next equals to head
Linked list and trees are recursive data types (you can read about these data types here).
In the case of trees, I would recommend to consider to pass to the helper function both the node and the child.