Introduction

In our 3rd article in this GALA series [1], we discussed  Recursion as a powerful concept that enables to design and develop simple, elegant and succint algorithms  for solving many computational problems. Recursion  is often used when solving problem using most of the  known algorithmic approaches [2][3], such as, divideand-conquer paradigm (or transform-and-conquer),  tree traversal, dynamic programming etc. Succinct  algorithms leads to easy visualization of problems and  enables a developer to easily read and write recursive  code. Even though any recursive code consists of two  parts: a) base case where problem can not be expressed  in another smaller self similar form and solved directly,  b) recursive case, where problem is expressed or  visualized in a smaller, often self similar form (though  not necessary) and using the solution of this smaller  self similar form, the solution of the original problem is  derived. The experience of this author when teaching  recursion to 1st and 2nd year computer science  undergraduate students has been that students find it  challenging to use recursive approach when base case  itself involve two or more parts and similarly and in  the recursive invocatino when one has to use two or  more smaller subproblems. The focus of this article is  to discuss such problems and enable students to apply  recursion in general problem solving.

As before, we will continue with our GALA (Gamified  Approach to Learn Algorithms) approach, and develop  solution perspectives using puzzles. The puzzles/ questions discussed in this article correspond to those  that were given to my undergraduate students and 50%  of the class found it challenging to solve it even when  they were given recursive equation in mathematical  form. These students could not visualize either multiple parts of base case or two or more smaller recursive version of the problem. 



Figure 1: Staircase climbing puzzle


Puzzle 1: The Staircase Climbing Problem.

In our daily lives, we often climb up stairs. Most of us take one step at a time, but sometimes we take a leap of two steps. So, puzzle question is in how many ways one can climb up a staircase of N steps. For example, if there is only 1-step stair case (Figure 1a) then there is only one way to climb up. If there is a two s stair case (Figure 1b), then there are two ways to climb up, which are as follows: first way is to take one step at a time and thus by taking two consecutive 1-steps we climb up the stair case. The second way is to take a leap of two steps in a single go. Similarly, consider a 3-steps staircase (Figure 1c). There are 3 ways to climb up which can be listed as (1),(2),(3) or (1,2),(3) or (1),(2,3). The first one refers to taking 1-step three times . The second case corresponds to first taking a leap of 2-steps, followed by taking 1-step. The last case refers to first taking 1-step followed a leap of 2-steps. When the staircase has N-steps (Figure 1d), then how do we count the number of ways. Elaborating like this will  become a tedious or complicated process. Recursive approach becomes very handy to solve this puzzle.

Consider a N-steps stair case. There are only two  choices: either climb 1-step or take a leap of 2-steps. In the former case, the number of steps remaining are  N-1 thus the problem of N-steps reduces to smaller  size problem of N-1 steps. Similarly, in the latter case  number of steps to climb up further are N-2 and problem size reduces to smaller case of N-2 steps. Thus, if climb(N) represents the number of ways to climb the stair case, then it can be solved in two ways by solving climb(N-1) and climb(N-2). Thus, for N>2, the number of ways will be climb(N-1)+climb(N-2). The recursive code for this is given in Table 1a. The base case in this recursive implementation consists of 2 parts where N=1 or N=2. Similarly, there are two similar smaller problems whose solutions need to be combined to arrive at a final solution. It is found that students often make the mistake of adding 1 when combining the results from smaller problems. The computation of 1+climb(N-1)+1+climb(N-2) is erroneous since 1-step followed by climb(N-1) represents only one way and does not correspond to two ways. Similarly, (1,2),(climb(N-2)) represents 2nd way because the hop of first 2-steps (1,2) combined with climb(N-1) is a single solution. Few initial value of number of ways are computed as climb(1)=1, climb(2)=2, climb(3)=3, climb(4)=5, climb(5)=8, climb(6)=13, and so on. A simple cursory looks shows that these value correspond to well known Fibonacci series.

Table 1: Recursive implementaion for climbing stair case



Let us consider a variation of this problem. Consider an enthusiastic child which can also take a hop of 3 steps in one go when climbing the stair case. Will our answer vary? At this step readers are requested to work out the solution before proceeding further.

In this case, where a child can leap either 1, 2 or 3 steps at a time, the base case will have 3 parts. When N=1, there is only 1 way possible. When N=2, then there are two ways to climb, that is, (1),(2) or (1,2). When there are 3-steps stair case, there are 4 possible solutions as given below: 

Always take one step at a time i.e. (1),(2),(3)

First take leap of 2 steps, followed by 1 step, i.e. (1,2),(3)

First climb 1 step followed by leap of 2 steps, i.e., (1),(2,3), and 

A single hop of 3 steps (1,2,3)

With N-steps stair case (N>3),the recursive approach now needs to combine the solutions of 3 smaller problems i.e.
climb(N-1), climb(N-2) and climb(N-3). The 
recursive implementation is given in Table 1b.

Puzzle 2: Counting Number of Paths (Manhattan Paths) in a Grid

Each one of us almost on daily basis criss cross number of streets in a city when moving from one place to another. A simplistic view of such street crossings in a city is shown in Figure 2. It shows a grid of n rows and m columns. A person starts from grid location (0,0)and need to reach the grid location (m,n). The person can reach the destination in many ways. For simplicity, we will consider that person does not move back. Thus, person can either move Right (R) or Up (U). One simple approach would be to keep moving right till reach the location (m,0) and then keep moving up to reach (m,n).Alternatively, one starts with moving up first all the way to location (0,n) and then moves right to reach (m,n). However, at any grid point, (i,j), 0<=i<=m,and 0<=j<=n, the person can move Right to location(i,j+1) or move up to location (i+1,j). The question to be answered can we count the number ways the person can move from initial starting grid point (0,0)to destination grid point (m,n).


Figure 2: Number of paths in a Grid

Before proceeding further, you are requested pause reading this article, and explore the answer. A typical approach to count all the number of ways would be tedious and complex. Use of recursive approach provides an simple and elegant solution. To solve this problem recursively, let us consider the base case i.e. the cases where solution is straight forward and person can move only one way. Consider the case that when a person has moved to extreme right, that is, last column m irrespective of row number j, which can be represented by grid point (j,m), then that person can only move up and there are no other choices available and hence number of ways would be 1. This is shown by horizontal pink arrow in bottom row in right side grid of Figure 2. Thus, having reached the last column, there is only one way possible to reach the destination. Similarly, when a person has reached the grid point (n,i) i.e in top row irrespective of column i, then that person has only oneway to move i.e. can only move right. This is shown by upward blue arrow in first column of right side grid of Figure 2. Thus, in our recursive implementation, recursive function will have two formal parameters column and row, and each recursive invocation, either column will increase by 1 or row will increase by 1. Whenever column becomes m or row becomes n, then there is only one way and these two situations will make the base case. Now let us consider the similar smaller problem. Consider that at some point, person has reached grid point (i,j). At this point problem still remains the grid problem but with grid size of (m-i)columns and (n-j) rows. From this grid point (i,j), if the person moves right, then next grid point would be(i,j+1) and if the person moves up, the next grid point would (i+1,j). Thus at any grid point except the last column or top row, person has two choices. Thus if the recursive function grid(i,j) represents the solution of counting number of ways to reach the destination,
then grid(i,j)=grid(i+1,j)+grid(i,j+1)provided i<m, and j

Table 2: recursive implementation for counting ways in grid

the code for recursive function is given in table 2. This function is invoked with the call grid(0,0). In this code, it assumed that values m, and n are global parameters.

Let count(mxn) represents the number of ways for grid of size mxn. Then a simple execution of the program provides the following answers.

count(1,1)=2, and the corresponding paths are0,0->0,1->1,1, and 0,0->1,0->1,

count(2,2)=6 and the corresponding paths are

a.     0,0->1,0->2,0->2,1->2,2
b.     0,0->1,0->1,1->2,1->2,2
c.     0,0->1,0->1,1->1,2->2,2
d.     0,0->0,1->1,1->1,2->2,2
e.     0,0->0,1->1,1->2,1->2,2
f.     0,0->0,1->0,2->1,2->2,2
To trace and print all the paths, the recursive code can 
be enhanced to print the resulting path and is left as an 
exercise for the reader.

Puzzle 3: Tiles Arrangement



Figure 4: Domino laying either vertically or horizontally

Another interesting puzzle involving recursion is to solve the problem of arranging a domino tile of size 3x1 in a floor of size 3xN. This is shown in Figure 3. The domino tile of size 3x1 can either be placed vertically or horizontally as shown in Figure 4. The requirement is that all the squares of the floor should be covered and no square should be left uncovered as well as each square can be covered only by one domino tile. You can assume that N number of domino tiles are available since N domino tiles will cover the entire area of 3xN. So, the question is to count number of ways in which these domino tiles can be placed on the floor. Before proceeding to discuss the solution, author recommends that you pause and work it out using recursive approach. Again, there are multiple base cases and each recursion invocation will depend upon two or more similar smaller solutions.

The solution lies in identifying the smaller size of similar subproblems. When we lay the domino tile vertically, then we are left with floor area of 3x(N-1) as shown in Figure 4, i.e. it becomes a smaller problem of sizeN-1. If we lay the domino tile horizontally in top row as shown in right side of Figure 4, then we are forced to lay two domino tiles horizontally in middle and bottom row. When that happens, then the remaining floor area becomes 3x(N-3) i.e. we need to solve the smaller problem of size N-3. Since in a 3xN floor, there are only 2 ways to lay the domino tile, the recursive solution will consist of using both the sub problems. Similarly, the base case consists of 3 parts which are as follows. If N=1, and in that case there is only 1 way to lay domino tile i.e. vertically. If N=2, then again domino tiles can be laid only vertically and hence there is only 1 way. If N=3, then domino tiles can either be laid vertically or horizontally and thus there are just 2 ways. When N>3,then we need to use recursisve solution using smaller sub problems. The recursive function implementation is shown in Table 3.

Table 3: Recursive implementation for laying domain tiles

Puzzle 4: Coin Tosses and  Computation of Number of Heads (Binomial Coefficients)
Consider the game of tossing a fair coin N times. Each toss of a coin can either show Head or Tail. Thus, in N tosses, we can get minimum of 0 heads (or tails) and maximum of N heads (or tails). Thus, in N tosses of a coin, we can get k heads where 0<=k<=N. The puzzle question is in how many ways these k heads can appear. For the base case, when k=0 i.e. no head appears in any toss or when k=N when each toss shows the head, there is only one possible way. When k=1, then there are only N possible ways since only 1 of the coin toss will show the Head and all other tosses will show the Tail. The number of ways for k heads in N tosses is given by binomial coefficient , which is computed as n!/(i!(n-i)!. The binomial coefficient corresponds to the coefficient of the term aibn-I in the polynomial expression of (a+b)n as shown in Equation 1. The polynomial expression for n=0,1,2,3,4 and 5 is shown in first column of Table 4. The second column shows the coefficient’s value, which is known as Pascal Triangle.


Table 4: Pascal Triangle


The typical computation for binomial coefficient  is done by computing 3 factorials. However, for any undergraduate student, when writing any C or Java program to compute using factorials, the computation works till n=12 and it fails to compute for n>12 since in C or java, int typically uses 32 bits (or 4 bytes) and when computing factorial of 13 or higher numbers, integer overflow occurs and results are incorrect. Even within limitation of 4 bytes for an integer, we can do better when we look at the problem in a different way. A close look at the values in Pascal triangle shows that except for the first and the last value in a row which is equal to 1, any other value is equal to sum of two other values (immediately placed above it) in the upper row. For example, value 10 (3rd and 4th value in row 6) corresponds to sum of 4 and 6 (2nd and 3rd values in row 5). In the Pascal triangle, kth value in nth row is given binomial coefficient , which can be computed as shown in Equation 2.

However, use of recursion to computer binomial coefficient makes it simple and elegant. The recursive approach is visible from the values in Pascal Triangle as shown in Table 4. The column on the left gives the polynomial expression successively for n=0, 1, 2, 3, 4, and 5, and right column of Table 4 defines the Pascal triangle. In the Pascal triangle, row number n lists all binomial coefficients for (a+b)n. As can be easily seen that each coefficient is sum of two left and right sides values in previous row which appear just above the coefficient. For the coefficients on extreme left and right, only one value i.e. 1 is taken. This leads to simple recurrence relation as given in Equation 2. The recursive implementation where the problem size of (n,k) is reduced to two problems of smaller sizes of (n-1,k) and (n-1. K-1). The leftmost and rightmost values in any row of Pascal Triangle corresponds to two bases with . The program using recursion is given in Table 5.

The elegance of recursive approach in computing binomial coefficients can be immediately noticed in its implementation as shown in Table 5. In this recursive implementation, there is no multiplication operation, no factorial computation, but a simple manifestation of Pascal’s Triangle just by using addition. Tracing out of values for binomcoeff(n,1) results in n times addition of integer 1. For most students, it initially comes as a big surprise or disbelief, as they only know that this computation requires repeated multiplication. The students appreciate this implementation when they invoke this function call with few values and trace out the execution.
This recursive implementation is one of few unique cases which helps student in understanding recursion and its application in designing elegant solutions to the problems at hand.

Table 5: Binomical Coefficient Computation using Recursion

Puzzle 5: Computing Sum of first N Natural numbers

In all of the four problems that we have discussed so far, the recursive case implementation consisted of mostly two subproblems. In some of the cases, the recursive case can involve more than 2 subproblems as well. We will discuss a simple problem of computing the sum of first N numbers that can be solved using more than 2 subproblems, each of approximately half the size of initial problem.

From the high school study of mathematics, we all have learnt that sum of first N natural numbers is equal to N(N+1)/2. Here we will analyze this problem from several different perspectives and explore the use of recursion in solving this problem in 3 different ways. Let S(n) represent the sum of first n natural numbers. Figure 5a shows the graphical representation of this problem, where top row contains one unit squares corresponding number 1, next row contains 2 unit squares corresponding to number 2, and nth row contains n unit squares. Now, computing S(n) is equivalent to count the number of unit squares since S(n)=1+2+…+n. One simplistic way to solve this counting problem is make a replica of this staircase like figure, and flip it vertically and horizontally and keep it on top of it as shown in Figure 5b. This gives a rectangle of size nx(n+1). Since this rectangle represents two times S(n), thus we get 2S(n)=n(n+1) S(n)=n(n+1)/2. This approach provides a simple and elgant solution in a non-recursive way.

  
Figure 5: Computing sum in non-recursive way

Now we will look at the same problem using recursive approaches and explore smaller similar sub-problems. One simple subproblem would be to compute S(n-1) i.e. sum of first n-1 natural numbers and then add n to this sum which gives the desired result. The decomposition into a smaller problem of size n-1 and corresponding implementation is shown in Figure 6. Line 02-03 in Figure 6b corresponds tobase case and lines 04-05 corresponds to recursive implementation.



 Figure 6: Approach 1: computing S(n) using simple recursion

Now, we will look at this problem from a different perspective and dividing the original problem into multiple subproblems. One simple way to decompose the problem of computing S(n) into similar subproblems is shown in Figure 7.



Figure 7: Approach 2-Decompoistion using 4 similar sub problems

Figure 7a shows the decomposition when n is even. In this case there are 3 subproblems of size n/2 and one subproblem of size n/2-1. Thus, when n is even then S(n) will be computed as S(n)=3S(n/2)+S(n/2-1). Similarly, if n is odd, the problem S(n) can be decomposed in 3 subproblems of size (n-1)/2 and one subproblem of size (n+1)/2as shown in Figure 7b. Thus, when n is odd, S(n) is computed as S(n)=3S((n-1)/2)+S((n+1)/2).The purpose of elucidating this deliberately convoluted composition is to show the different approach that can be taken to solve a given problem. The essential idea is to look at a given problem and explore its visualization in its smaller avatars and once we reach a base case of smallest size subproblem, then build upon the solution  from there onwards. Thus, we would like to stress that  recursive implementation is not restricted to only 1 or 2 subproblems but can have as many subproblems as required. The recursive implementation using this decomposition is shown in Table 5. In this recursive implementation, the base case (lines 02-03) has only one component whereas recursive part (lines 04-07) deals with 4 components separately for when n is even and n is odd.

Table 6: Recursive implementation using 4 subproblems

In both of the above approaches, our smaller subproblems were similar to the original problem. However, this is not a necessary condition for recursive approaches. At times, one may have to decompose 
the problem into a different type of subproblems and build upon solution for the same. Figure 8 shows the decomposition of S(n) in a different way. S(n)is decomposed into 2 similar subproblems and one different type of subproblem of computing square of a number. Since n can be either even or odd, the decomposition needs to work in both cases as shown in Figure 8.


Figure 8: Approach 3-Using 2 similar and 1 dissimilar problems

The recursive implementation using approach 3 is shown in Table 7. Lines 07-08 corresponds to base case and lines 09-12 corresponds to recursive invocation of smaller problems. The computation of square is also implemented using simple recursive approach (lines 01-05). Even this square computation can be implemented by decomposing it into problem size of n/2 when n is even and problem size of (n-1)/2 when n is odd. This is left as an exercise to the reader.

Table 7: Recursive implementation using approach 3

Summary

In this article we have tried to understand recursive approach by decomposing the original problem into several subproblems (not limited to just 1 or 2 subproblems), which may be either of similar types or even of different types. When we make use of different size subproblem in recursive invocation, this is known non-linear recursion. We have also looked at variations in base case problems i.e. different smallest sub problems which can not be decomposed further and must be solved by known means. The base cases need not be restricted to single case and can have multiple smallest cases which needs to be solved separately. The beauty and elegance of using recursive approach lies in the fact that one should be able visualize given problem into smaller problems and once this visualization is accomplished, then one has to just combine the solution of smaller sub problems to find the answer to the original problem. The crux of recursion lies in that one must be able to identify the right base case. Further, in any recursive implementation (code or programs), one should address the base cases first. Not adhering to this guiding principle, recursive implementation will go into infinite loop and author has seen many students making such mistakes often and then struggling with debugging the programs.

Exercises

To help understand the nuisances of recursive implementation, given below are few exercises in Table 8, some of which have deliberately concocted base cases. You are requested to trace out the execution of the computation and understand the different approach of using either base case or recursive implementation. This is to just to show that at times, when looking at base cases, it may not be necessary to identify the base case with problem of size 0, 1 or 2. This can be any other value as well. Exercise 1 shows implementation of factorial computation where base case corresponds to largest value i.e. n itself whose factorial is being computed. Exercise 2 shows the recursive implementation of sum(n) but with a base case of using n=-1. In this implementation, irrespective of whether the base case is taken as n=0 or n=-1, answer does not change. This example is taken just to show a convoluted implementation of base case. Exercise 3 corresponds to computing negative of sum of first n natural numbers. Tracing out each of these exercises, will help the reader in better understanding of use of base cases and recursive invocation.

Table 8: Exercises for tracing recursive implementation

References

Ram Rustagi, Viraj Kumar, GALA: Exploring Basics of Algorithmic Approach, ACS Publication on Computing and Communications, September 2021, Volume 5 issue 3. https://journal.accsindia.org/show.article.php?id=113

Anany Levitin, “Introduction to the Design and Analysis of Algorithms”, 2nd edition, Pearson Education.

Manuel Rubio Sanches, “Introduction to Recursive Programming”, October 2017, CRC Press.