Earlier we had looked at the structure of a linked list and demonstrated an iterative java program to reverse it. In this entry, the stress would be on recursively implementation.
What is recursion and why is it used?
Recursion is the process of solving a complex problem by breaking it into smaller subproblems that are easy to solve. It is a decompositional technique and a variety of computer problems make their way into easily being resolved through the art of recursion. For instance: divide and conquer algorithms such as merge sort, reversing a linked list, towers of hanoi etc.
The easiest way to provide a recursive solution to a complex problem is to break down the problem into subproblems and so on till the subproblems are easier to comprehend and consequently easier to solve. For instace, lets break down the problem of reversing a linked list.
We will examine a similar linked list to that in an earlier blog entry (A->B->C->D).
if size = 1 then there is no need to do anything
if size = 2 then traverse to the node 2 and then reverse pointer from 2 to 1
if size = 3 then traverse to node 3 and then reverse pointer from 3 to 2 and then perform the steps outlined above
and so on. This leads us to a solution of the problem recursively
static Node reverseRecursive(Node n, Node previous, Node end)
if (n.next != null)
end = reverseRecursive(n.next, n, end);
end = n;
n.next = previous;
The primary advantage of recursion is that it is simple to implement as the mathematical concepts can be easliy translated into a recursive solution.
The disadvantage is the fact that there is a lot of overhead of the recursive method invoking itself repeatedly. This leads to method arguments, method return addresses etc being stored in stack.
Iterative program to reverse a linked list has been elucidated in an earlier blog entry.