Understanding Recursion in C# : A Practical Approach


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 to 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 the 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

Recursion calls itself to solve other pieces of a problem until all pieces get 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 steps 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.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 the 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 methods 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 examples 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 the 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 the 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);
    6. }

     

  • 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 visualise the structure of the directory by the following drawing:DIRECTORY

    In the above tree diagram, the  colour nodes represent files and blue represents subdirectories.
    So are we going to this problem using recursion? Firstly we will get all the files present in the parent directory and if parent directory contains sub-directories then the recursive call is made. Base case in this problem is that a directory does not contain any subdirectory. Reduction step is to pass the subdirectory name.

    In this problem, we have used iteration as well to get the desired result because a directory may contain more than one subdirectories and we have to get files from each subdirectory.

    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;
    6. namespace Console Application2
    7. {
    8.     class Program
    9.     {
    10.         static void Main(string[] args)
    11.         {
    12.             WalkDir(“DirectoryPath”);
    13.         }
    14.         public static void WalkDir(string dir)
    15.         {
    16.             try
    17.             {
    18.                 var files = Directory.GetFiles(dir);
    19.                 foreach(var file in files)
    20.                 {
    21.                     Console.WriteLine(file);
    22.                 }
    23.                 var subDirectories = Directory.GetDirectories(dir);
    24.                 foreach(var subDir in subDirectories)
    25.                 {
    26.                     WalkDir(subDir);
    27.                 }
    28.             } catch (Exception)
    29.             {
    30.             }
    31.         }
    32.     }
    33. }

     

  • Walk the DOM 

    It is very common practice to walk the DOM elements in JavaScript to perform a certain task. As we know a node element in HTML page can contain 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.BODY

    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. The 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. {
    3.     // do something with the node
    4.     var children = node.childNodes;
    5.     for (var i = 0; i < children.length; i++)
    6.     {
    7.         WalkDOM(children[i]);
    8.     }
    9. }

     

  • 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”: [{
    29.                 “Title”“Topic 1”,
    30.                 “Nodes”: []
    31.             }, {
    32.                 “Title”“Topic 2”,
    33.                 “Nodes”: []
    34.             }]
    35.         }, {
    36.             “Title”“Chapter 2”,
    37.             “Nodes”: [{
    38.                 “Title”“Topic 2.1”,
    39.                 “Nodes”: []
    40.             }]
    41.         }]
    42.     }]
    43. }];

     

    We want to parse the above object to make a nested listed as shown in the below figure:

    NESTED

    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 contain 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 the number of objects. If the object contains the nested object then the same process is repeated hence recursion. The base case is until the 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&#8221;>
    3.     <head>
    4.         <title></title>
    5.     </head>
    6.     <body>
    7.         “list”>
  •                 var listObj = [{
  •                     “Title”“UNIT 1”,
  •                     “Nodes”: [{
  •                         “Title”“Chapter 1”,
  •                         “Nodes”: [{
  •                             “Title”“ABC”,
  •                             “Nodes”: []
  •                         }]
  •                     }, {
  •                         “Title”“Chapter 2”,
  •                         “Nodes”: [{
  •                             “Title”“XYZ”,
  •                             “Nodes”: []
  •                         }]
  •                     }]
  •                 }, {
  •                     “Title”“UNIT 2”,
  •                     “Nodes”: [{
  •                         “Title”“Lorem Ipsum”,
  •                         “Nodes”: []
  •                     }]
  •                 }, {
  •                     “Title”“UNIT 3”,
  •                     “Nodes”: [{
  •                         “Title”“UNIT 3.1”,
  •                         “Nodes”: [{
  •                             “Title”“Chapter 1”,
  •                             “Nodes”: [{
  •                                 “Title”“Topic 1”,
  •                                 “Nodes”: []
  •                             }, {
  •                                 “Title”“Topic 2”,
  •                                 “Nodes”: []
  •                             }]
  •                         }, {
  •                             “Title”“Chapter 2”,
  •                             “Nodes”: [{
  •                                 “Title”“Topic 2.1”,
  •                                 “Nodes”: []
  •                             }]
  •                         }]
  •                     }]
  •                 }];
  •                 var list = document.getElementById(‘list’);
  •                 var createTree = function(arr)
  •                 {
  •                     var ol = document.createElement(‘ol’);
  •                     for (var i = 0; i
  •                         var li = document.createElement(‘li’);
  •                         li.innerHTML = arr[i][“Title”];
  •                         if (arr[i][‘Nodes’].length != 0) {
  •                             li.appendChild(createTree(arr[i][“Nodes”]));
  •                         }
  •                         ol.appendChild(li);
  •                     }
  •                     return ol;
  •                 }
  •                 list.appendChild(createTree(listObj));
  •     </body>
  •     </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 the 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 is centred in the four quadrants of the square, halved in size.GRAPH
    Let’s see the code to draw the above recursive graph.

    1. <!DOCTYPEhtml>
    2. <html xmlns=http://www.w3.org/1999/xhtml&#8221;>
    3.     <head>
    4.         <title></title>
    5.     </head>
    6.     <body>
    7.         <canvasid=“paper” width=“1200” height=“700” style=“border:1px solid”>
    8.             </canvas>
    9.                 // function to draw H shape design
    10.                 function drawH(x, y, size)
    11.                 {
    12.                     var x0 = x – size / 2;
    13.                     var x1 = x + size / 2;
    14.                     var y0 = y – size / 2;
    15.                     var y1 = y + size / 2;
    16.                     var c = document.getElementById(‘paper’);
    17.                     var ctx = c.getContext(‘2d’);
    18.                     ctx.beginPath();
    19.                     ctx.moveTo(x0, y0);
    20.                     ctx.lineTo(x0, y1);
    21.                     ctx.moveTo(x0, y);
    22.                     ctx.lineTo(x1, y);
    23.                     ctx.moveTo(x1, y0);
    24.                     ctx.lineTo(x1, y1);
    25.                     ctx.stroke();
    26.                 }
    27.                 function draw(n, x, y, size)
    28.                 {
    29.                     if (n == 0)
    30.                         return;
    31.                     drawH(x, y, size); // draw H shape
    32.                     var x0 = x – size / 2;
    33.                     var x1 = x + size / 2;
    34.                     var y0 = y – size / 2;
    35.                     var y1 = y + size / 2;
    36.                     draw(n – 1, x0, y0, size / 2); // recursion to draw four H shape at each corner of H
    37.                     draw(n – 1, x0, y1, size / 2);
    38.                     draw(n – 1, x1, y0, size / 2);
    39.                     draw(n – 1, x1, y1, size / 2);
    40.                 }
    41.                 draw(4, 200, 200, 50) // calling draw method
    42.     </body>
    43.     </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. A 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.

Advertisements

Author: Vikas Sharma

I am currently working as a Software Engineer in Magic Software and have an experience of more than a year in C#.Net. I have my graduation in Bachelor of Computer Applications and hold a diploma in Software Engineering GNIIT from NIIT. I am very passionate about programming, love to learn new technology and believe in sharing knowledge. My work experience includes Development of Enterprise Applications using C#,.Net,Sql Server,AngularJS and Javascript.