Recursive method design

In general, you need to think about a recursive method as any other type of problem you need to solve with loops.  Since recursive methods are nothing more than counter controlled while loops.  In every loop, you have to think about what to accomplish and what to update in addition to when to stop.

Let's take a simple example of adding values from 0 to some predetermined value.

First, you will need to design the algorithm based on your math knowledge. Thus, it might look like this,

As you can see the last term in the equation can be expressed in the terms of summing all values to n-1 and adding the next value to get the total sum of the values.  Thus, we have to understand that we have a previous value that exists.  Therefore, we have to stop when i equals n since there is no previous value before i==n, in that case the result is just n.

Let's solve this using regular loop:
 

Code Snippet

1. public class Recursive{
2.     public static void main(String args[]){
3.         final int lowerLimit = 1;
4.         int upperLimit = 10, sum = 0;
5.         while (upperLimit > 0){
6.             sum += upperLimit;
7.             upperLimit--;
8.         }
9.         System.out.println(sum);
10.     }
11. }

Now, we can take this loop based solution and try to solve it by calling the function with a trivial solution like when the upper and lower limit is equal.

public class Recursive {
 public static void main(String args[]) {
  int upperLimit = 1, sum;
  sum = recurse(upperLimit);
  System.out.println(sum);
 }
 
 private static int recurse(int upperLimit) {
  int sum = 0;
  final int lowerLimit = 1;
  while (upperLimit >= lowerLimit) {
   sum += upperLimit;
   upperLimit--;
  }
  return sum;
 }
}

We now have solved a trivial value, next we need to see if we can solve the next value by adding all the previous values together.

public class Recursive {
 public static void main(String args[]) {
  int upperLimit = 2, sum;
  sum = recurse(upperLimit - 1) + 2;
  System.out.println(sum);
 }
 
 private static int recurse(int upperLimit) {
  int sum = 0;
  final int lowerLimit = 1;
  while (upperLimit >= lowerLimit) {
   sum += upperLimit;
   upperLimit--;
  }
  return sum;
 }
} 

So, now we proved that our method works with summing n-1 + n when a method is called with n-1.

Now, we can try to modify the method to call itself with n-1 values until it reaches 

the trivial value of lower limit.

Our goal is to call the method with n-1 as the parameter until we reach the trivial case 

that will reverse the course and return values that we'll add to n.

3 + f(2) -> 6

2 + f(1) -> 3

    f(1) -> 1 

public class Recursive {
 public static void main(String args[]) {
  int upperLimit = 10, sum;
  sum = recurse(upperLimit);
  System.out.println(sum);
 }
 
 private static int recurse(int upperLimit) {
  int sum = 0;
  final int lowerLimit = 1;
  if (upperLimit == lowerLimit)
   return upperLimit;
  else
   sum = upperLimit + recurse(--upperLimit);
  return sum;
 }
}

Now, we eliminated the loop due to recursive method calls and proved the original assumption of adding the upperLimit to the sum of all previous elements provides the sum of all elements.