Recursion - Sums in a Triangle

An Introduction

Recursion, by definition, is a method of defining a function in a way such that the function being defined is applied within its own definition. A lot of problems in computer science can be broken down into smaller sub-problems. Most of these can have recursive solutions where the answer for each state is calculated from answers of smaller sub-states. Recursion, however, is very inefficient and most of the times, the answers for a particular state are calculated again and again. To overcome this limitation, a technique called memoization can be used. Memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously-processed inputs.

Thus, if the answers for each visited state are stored in a cache of sorts in the recursive solution, we can avoid re-calculating values we have already calculated.

We will see how to use these techniques to solve one of the easy level problems on Codechef.

Problem Tutorial - Sums in a Triangle

Sums in a Triangle http://www.codechef.com/problems/SUMTRIAN represents a broad range of problems that can be solved by using a recursive approach. As such, we will see one of the methods to solve it.

The problem asks one to take as input the number of test cases as the first input. Each test case consists of the number of rows 'n' and then 'n' lines follow containing each row.

The first row has 1 number, the second has 2 numbers, the 3rd has 3 numbers and so on. Now, We have to find a path from row 1 to row 'n' such that the cost of the path is maximized.

The cost of a path is the sum of all the numbers that make up the path. The additional constraint is that from a particular cell, we can only go to a cell in the next row directly beneath the cell or to the one situated to the right of the one beneath it. We start off in the topmost row and in its left most cell.

A very naive way to do this is to generate all paths, find the cost of the paths and choose the best one. Such an approach would time out because we can have a max of 100 rows.

Now, to model a problem in a recursive manner, we need subproblems which are similar to the problem to be solved. The prerequisites to modelling a recursive solution are

1. There should be subproblems

2. There should be terminating conditions called base conditions.

3. The sub-problem to be solved must be the same as the parent problem, but of a smaller magnitude or size.

4. There should be no cycles. One should not be able to reach a state, by starting off from it.

1. First of all, we need to find subproblems. Consider a particular cell (i, j). From this cell, we can go either to cell (i + 1, j) or (i + 1, j + 1), where the first index represents the row and the second one represents the columns. Now, we need to maximize the sum for paths from cell (0, 0). Now, the maximum path value for cell (0, 0) will equal the value at cell(0, 0) + max(value of max path from cell(0, 1), value of max path from cell(1, 1)) Thus, we get the subproblems that we were looking for. The max path value at a particular cell equals the value at that cell + the max path values of cells reachable from it.

2. We can fix the terminating conditions as follows. The value of the max path if we reach a row beyond the 'n' rows specified is 0. This becomes our stopping condition for each path.

3. The subproblem to be solved is the same as the original problem. At each step we are making the size of the rows to be checked lesser and lesser and moving towards our base condition.

4. There are no cycles. There won't be a path such that we start from cell (i, j) and move on to some cells and reach cell(i, j) again. This can be seen by the fact that at each step, the row number keeps on increasing. It never decreases also, it never remains the same.

Thus, having modelled it as a recursive solution, we can create a recursive solution to the problem as follows.

Function solve(i, j)

if i is greater than 'n'

return 0

t1 equals solve(i + 1, j)

t2 equals solve(i + 1, j + 1)

t equals max(t1, t2) + value at cell(i, j)

return t

This simple recursive function will get us the answer for the path with the maximum cost. This will work for small values of 'n'. One thing that we notice is that in the given situation, we might end up calculating the value of the max path from a particular cell more than once. We can reach (3,2) in two ways. (1,1)>(2,1)>(3,2) and (1,1)>(2,2)>(3,2). The max value path from (3,2) will be calculated more than once even though we get the answer for it, the first time. A simple way to overcome this is to cache the value for the path from (3,2) the very first time we calculate it. A simple change to the function will give us the required effect.

Function solve(i, j)

if i is greater than 'n'

return 0

if i, j has been visited before

return cache(i, j)

t1 equals solve(i + 1, j)

t2 equals solve(i + 1, j + 1)

t equals max(t1, t2) + value at cell(i, j)

cache(i, j) equals t

return t

This technique is called recursion along with memoization. An analogous technique is Dynamic Programming which involves building the answer by using a bottom-up approach instead of the top-down approach used in the current method. A lot of problems which involve maximizing or minimizing values or which involve counting the number of patterns etc can be calculated using this technique.

Recursion Problems on CodeChef

The below mentioned problems can be solved once one understands the techniques mentioned in the tutorial.

http://www.codechef.com/problems/COINS

http://www.codechef.com/problems/MIXTURES

http://www.codechef.com/problems/MENU

Activities on Campus

Conduct a session on Campus:

Once a Chapter member solves one of the above mentioned practice problems he/she can conduct a session where the solution is explained to other participants/members on Campus. If required, this can be done with the help of a professor as well.

Other useful links

http://en.wikipedia.org/wiki/Recursion_%28computer_science%29

http://en.wikipedia.org/wiki/Memoization

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=recursionPt1

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=recursionPt2

http://www.cprogramming.com/tutorial/lesson16.html

http://www.ibm.com/developerworks/linux/library/l-recurs.html