Fun with Recursion: back to basics.

I am currently working on solving a problem that is about trees, lots and lots of them. Looking at this problem, the first thing I realised was that, while I can solve this problem using stacks, this is really a problem for which a recursive solution is a natural fit. Recursive problem solving is something that I have quite lost the hang of in recent years, using only iteration on a day to day basis.

Hence I decided to go about rectifying it and learning what is essentially early uni years stuff. This is harder than it sounds, not because of the problem itself but because of how "dumb" I felt, given that this is really something that I should be naturally good at. Now once I got over my emotional issues and hours of self loathing, I actually had a strategy of how I can get better at recursion.

The strategy was simple, forget about my work experience, the education, the scientific publications etc etc, all in all swallow my pride and start from the very beginning by first properly understanding recursion and then by solving some really really simple problems recursively. The long term goal was to try and recursively solve all the problems that I solve iteratively on a day to day basis. Obviously the biggest challenge was to visualise the entire recursive solution unfold in my head and this actually did not happen until I had solved atleast 10 or 20 problems.
 
So what is recursion? it is a process through which a function calls itself (for java, a method that calls itself). So one way of thinking about it is that, take one big problem, break it down into N sub-problems and then write a function that solves one sub-problem and call itself N times, combines the output of all those calls and solves the overall big problem. Now let us illustrate that, lets take the "big" problem of computing the sum of all numbers from N to 0. The solution to this is below

public int sum(int n) {
    if(n == 1) {
        return n;
    }
    return n + sum(n-1);
}

 
Ok so recursion is about making multiple function calls to solve individual sub-problems until the big problem is solved, so the first thing to figure out is when do we know that we have reached the last sub-problem? i.e. we need to find out the termination condition, which in the above example is 1. Ok i am getting ahead of myself here. Let us visualise each function call of the above method. So invoking sum(3) would do the following.

3 + sum(3-1)  in the first function call
2 + sum(2 - 1) in the second function call
return 1, since N will be 1 in the third function call, we have reached the last sub-problem, therefore we stop here.

Therefore sum(2-1) evaluates to 1,  sum(3-1) evaluates to 3 and the overall "big" problem sum(3), evaluates to 6. Ok now equipped with the core knowledge of recursive problem solving, lets solve some more problems recursively.

Problem 1: Find the min value in an array

public int findMin(int[] a, int size) {
    if (size == 0) {
        return a[size];
    }
    int min = findMin(a, size - 1);
    if (a[size] < min) {
        return a[size];
    } else {
        return min;
    }
}

Problem 2: Reverse a string recursively

public String recursiveStringReverse(String str) {
    if (str.length() < 1) {
        return str;
    }
    return recursiveStringReverse(str.substring(1)) + str.charAt(0);
}

Problem 3: Compute the sum of all the elements in a 2D array

public int sum(int[][] grid, int x, int y) {
    if (x == grid.length) {
        return 0;
    }
    if (y >= (grid[x].length - 1)) {
        return grid[x][y] + sum(grid, x + 1, 0);
    }
    return grid[x][y] + sum(grid, x, y + 1);
}

Recursive problem solving is a lot of fun and it is most certainly something that i really wouldn't want to loose the hang of. One of the things i found very helpful during this exercise were the problems  found at Coding Bat, all the problems provided on their site are pretty handy and a great way to start practicing some recursive problem solving.