Fun with Recursion

I am currently working on solving a problem that is about trees. 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 lost the hang of in recent years, since I write iterative solutions on a daily basis. Anywho, in this post let’s have some fun with recursion 🙂

Hence I decided to go about rectifying it and learning what is essentially early university years stuff. This is harder than it sounds, not because of the problem itself but because of how “dumb” I felt, given this is 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 understanding recursion and then by solving some simple problems recursively. The long term goal was to try and recursively solve all the problems that I solve iteratively on a daily 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 at least 10 or 20 problems.

Fun with Recursion

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.

If you find any of my posts useful and want to support me, you can buy me a coffee :)

https://www.buymeacoffee.com/bhumansoni

Or you can  buying or even try one of my apps on the App Store. 

https://mydaytodo.com/apps/

In addition the above, have a look at a few of the other posts,
How to create radio buttons using vanilla Javascript
https://mydaytodo.com/vanilla-javascript-create-radio-buttons/

How to build a Javascript frontend for Java Spring Boot backend 
https://mydaytodo.com/java-spring-boot-vanilla-javascript-solution/

Or have a look at some useful Javascript tutorials below
https://mydaytodo.com/category/javascript/