Recursion In Brief

Introduction

In our programming life there are situations where we have to write code to perform some repetitive tasks and in those situations recursion can become our best friend, but the problem with recursion is that it is sometimes complicated to understand.

Recursion is one of the topics that we all are taught in our student life but at that time we do not give much attention to this guy, and when we start our life as a programmer this same guy comes again in our life to irritate us and laugh at us.

So this is my little effort to introduce you to recursion so that you can use it in your code without any doubt and hesitation.

Though many of the problems can be easily solved using iteration and loops, there are some problems like graphs and tree where recursion can come in handy.

In this article I’ll be focusing more on algorithms rather than on programming language -- you can choose programming language of you own choice. For demonstration purposes I’ll be using JavaScript & C# because most of the programmers are familiar with the same.

Recursion

Wikipedia says “Recursion is a method where the solution to a problem depends on solution to smaller instances of the same problem.” What I understood is that we need to break the big problem into similar smaller pieces in order to tackle the complete problem. Divide and Rule.



Recursion calls itself to solve other pieces of problem until all pieces gets solved. There are two main components of a recursion method:

• The base case returns a value without making any further recursive calls. This is the step which stops recursive methods to run infinitely.
  
  
• The reduction step which is the main part. Basically it relates the function at one or more inputs to the function evaluated at one or more inputs. At the end sequence of input parameters should reduce to base value.
  
  
  

Let’s understand what is happening in the flow chart. In every recursive method there is a base case which terminates the function if condition is satisfied else the method calls itself to return the value or it may call itself successively and the chain continues unless one of the called method meets the required condition to terminate the chain.

We will understand the above points when we will solve some real problems.

Recursive problems

• Factorial
  
  One of the basic example of recursion is to write a program to generate factorial.
  
  N! =N*(N-1)*(N-2)*(N-3)…….. 4*3*2*1
  
  Let’s find out the base case for this problem.
  
  Base Case: If the N=1 then return 1 and terminate function.
  
  Reduction step: For this problem reduction step is N*Recursive Call(N-1). For any given number N we want to multiply that number with N-1, N-2, N-3 until we reach 1.
  
  Let’s find out the factorial of 3.
  
  3! =3*2*1 = 6
  
  
  
  I guess the above flow chart is self-explanatory. We have N=3 we pass it to function, base case N==1 is false in first case then in reduction step N is reduced by 1 i.e. 3-1=2 and it calls itself. Now we have N=2 and again base case is false so for the reduction step N becomes 2-1=1, and function calls itself, this time we have N=1 so the base is true and hence function terminates by returning the desired result.
  
  Let’s convert this algorithm into an actual program:
  
  1. function factorial(n)
  2. {
  3. if (n == 1)
  4. return 1;
  5. return n * factorial(n - 1);
  7. }
• Walk directory
  
  Let’s say you want to walk the directory to get the list of all files present in that directory as well as in all the sub-directories present that directory. Here directory structure can be thought of as a tree. As said earlier recursion can be very helpful in such cases. Try to visualize the structure of the directory by the following drawing:
  
  
  
  In the above tree diagram the color nodes represents files and blue represents sub directories.
  So are we going to this problem using recursion? Firstly we will get all the files present in parent directory and if parent directory contains sub-directories then recursive call is made. Base case in this problem is that a directory does not contain any sub directory. Reduction step is to pass the sub directory name.
  
  In this problem we have used iteration as well to get the desired result because a directory may contain more than one sub directories and we have to get files from each sub directory.
  
  Below is code snippet written in C# for the same:
  
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.IO;
  7. namespace Console Application2
  8. {
  9. class Program
  10. {
  11. static void Main(string[] args)
  13. {
  14. WalkDir("DirectoryPath");
  15. }
  17. public static void WalkDir(string dir)
  18. {
  19. try
  20. {
  21. var files = Directory.GetFiles(dir);
  22. foreach(var file in files)
  23. {
  24. Console.WriteLine(file);
  25. }
  26. var subDirectories = Directory.GetDirectories(dir);
  27. foreach(var subDir in subDirectories)
  28. {
  29. WalkDir(subDir);
  30. }
  31. } catch (Exception)
  32. {
  34. }
  36. }
  37. }
  38. }
• Walk the DOM
  
  It is very common practice to walk the DOM elements in JavaScript to perform certain task. As we know a node element in HTML page can contains child nodes further their children can also contain their own children. So in this case also recursion can be successfully used to walk the DOM.
  
  
  
  The algorithm is very simple in here. We need to traverse a node and all its children and if a child contains its own children then we need to traverse the children also. Base case is to traverse till a node contains children and reduction step is to pass each child in recursion one by one.
  
  1. function WalkDOM(node)
  2. {
  4. // do something with the node
  6. var children = node.childNodes;
  8. for (var i = 0; i < children.length; i++)
  9. {
  10. WalkDOM(children[i]);
  11. }
  12. }
• Nested list
  
  In this example we are going to make a nested list by parsing a nested object.
  
  The structure of our object is given below:
  
  1. var listObj = [{
  2. "Title": "UNIT 1",
  3. "Nodes": [{
  4. "Title": "Chapter 1",
  5. "Nodes": [{
  6. "Title": "ABC",
  7. "Nodes": []
  8. }]
  9. }, {
  10. "Title": "Chapter 2",
  11. "Nodes": [{
  12. "Title": "XYZ",
  13. "Nodes": []
  14. }]
  15. }]
  16. }, {
  17. "Title": "UNIT 2",
  18. "Nodes": [{
  19. "Title": "Lorem Ipsum",
  20. "Nodes": []
  21. }]
  22. }, {
  23. "Title": "UNIT 3",
  24. "Nodes": [{
  25. "Title": "UNIT 3.1",
  26. "Nodes": [{
  27. "Title": "Chapter 1",
  28. "Nodes": [{
  30. "Title": "Topic 1",
  31. "Nodes": []
  32. }, {
  34. "Title": "Topic 2",
  35. "Nodes": []
  36. }]
  37. }, {
  38. "Title": "Chapter 2",
  39. "Nodes": [{
  40. "Title": "Topic 2.1",
  41. "Nodes": []
  42. }]
  43. }]
  44. }]
  45. }];
  We want to parse the above object to make a nested listed as shown in the below figure:
  
  
  
  If we observe the object carefully we will find that the object basically contains an array of objects having two properties; one is Title and the other is an array of Nodes which may contains an array of nested objects.
  
  So the algorithm to create the list as shown above we need to traverse each object and create an ol list and add li item in it as per number of objects. If the object contains the nested object then the same process is repeated hence recursion. Base case is until object has nested object. Reduction step is to pass each nested in a loop.
  
  Below is the code snippet written in JavaScript for achieving the task:
  
  1. <!DOCTYPEhtml>
  2. <html xmlns="http://www.w3.org/1999/xhtml">
  4. <head>
  5. <title></title>
  6. </head>
  8. <body>
  9. <divid="list">
  10. </div>
  11. <script>
  12. var listObj = [{
  13. "Title": "UNIT 1",
  14. "Nodes": [{
  15. "Title": "Chapter 1",
  16. "Nodes": [{
  17. "Title": "ABC",
  18. "Nodes": []
  19. }]
  20. }, {
  21. "Title": "Chapter 2",
  22. "Nodes": [{
  23. "Title": "XYZ",
  24. "Nodes": []
  25. }]
  26. }]
  27. }, {
  28. "Title": "UNIT 2",
  29. "Nodes": [{
  30. "Title": "Lorem Ipsum",
  31. "Nodes": []
  32. }]
  33. }, {
  34. "Title": "UNIT 3",
  35. "Nodes": [{
  36. "Title": "UNIT 3.1",
  37. "Nodes": [{
  38. "Title": "Chapter 1",
  39. "Nodes": [{
  41. "Title": "Topic 1",
  42. "Nodes": []
  43. }, {
  45. "Title": "Topic 2",
  46. "Nodes": []
  47. }]
  48. }, {
  49. "Title": "Chapter 2",
  50. "Nodes": [{
  51. "Title": "Topic 2.1",
  52. "Nodes": []
  53. }]
  54. }]
  55. }]
  56. }];
  60. var list = document.getElementById('list');
  63. var createTree = function(arr)
  64. {
  66. var ol = document.createElement('ol');
  67. for (var i = 0; i < arr.length; i++) {
  69. var li = document.createElement('li');
  70. li.innerHTML = arr[i]["Title"];
  72. if (arr[i]['Nodes'].length != 0) {
  73. li.appendChild(createTree(arr[i]["Nodes"]));
  74. }
  75. ol.appendChild(li);
  77. }
  78. return ol;
  80. }
  81. list.appendChild(createTree(listObj));
  82. </script>
  83. </body>
  85. </html>
• Recursive graph
  
  We are going to create an H-tree of order n which the base is null for n=0. The reduction step is to draw, within the unit square 3 lines in shape of H four H-trees of n-1 order, one connected to each tip of the H in the manner that the H-trees of order n-1 are centered in the four quadrants of the square, halved in size.
  
  
  Let’s see the code to draw the above recursive graph.
  
  1. <!DOCTYPEhtml>
  2. <html xmlns="http://www.w3.org/1999/xhtml">
  4. <head>
  5. <title></title>
  6. </head>
  8. <body>
  9. <canvasid="paper" width="1200" height="700" style="border:1px solid">
  10. </canvas>
  11. <script>
  12. // function to draw H shape design
  13. function drawH(x, y, size)
  14. {
  15. var x0 = x - size / 2;
  16. var x1 = x + size / 2;
  17. var y0 = y - size / 2;
  18. var y1 = y + size / 2;
  20. var c = document.getElementById('paper');
  21. var ctx = c.getContext('2d');
  22. ctx.beginPath();
  24. ctx.moveTo(x0, y0);
  25. ctx.lineTo(x0, y1);
  27. ctx.moveTo(x0, y);
  28. ctx.lineTo(x1, y);
  30. ctx.moveTo(x1, y0);
  31. ctx.lineTo(x1, y1);
  33. ctx.stroke();
  34. }
  36. function draw(n, x, y, size)
  37. {
  38. if (n == 0)
  39. return;
  40. drawH(x, y, size); // draw H shape
  42. var x0 = x - size / 2;
  43. var x1 = x + size / 2;
  44. var y0 = y - size / 2;
  45. var y1 = y + size / 2;
  47. draw(n - 1, x0, y0, size / 2); // recursion to draw four H shape at each corner of H
  48. draw(n - 1, x0, y1, size / 2);
  49. draw(n - 1, x1, y0, size / 2);
  50. draw(n - 1, x1, y1, size / 2);
  51. }
  53. draw(4, 200, 200, 50) // calling draw method
  54. </script>
  55. </body>
  57. </html>

Conclusion

We leveraged the power of recursion in various situations. All we need to solve any problem with the help of recursion is to find the base case and the reduction step for given problem. Proper algorithm needs to be created before writing any code. I hope the above examples are interesting and easy enough to help you understand the basics of recursion.