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.

Design - Flowcharting and Pseudocode, function call and logic

Design is not just an annoying process in proper programming, but a necessary process to design code.
It can also eliminate misunderstanding in communication with others like in your marriage. Even in cooking, you would not start by turning on the oven to prepare dinner, but you would write down the shopping list before you left for the store and followed an ingredient list as you walked the isles. Planning is necessary when you want to accomplish something properly and design is necessary if you want someone else to create your idea, so you can come up with more ideas.

In all programming languages, we cover boolean logic and talk about the short circuits that exists with AND and OR boolean expressions. It is much easier to understand why they work if you can visualize its design. Boolean AND does not need to check the right side if the left side is false since there is not way to get a true result.  Only need to check the right side if the left side was true.
In boolean OR, there is no reason to check the right side if the left side is true since if will not be possible to get a false result.  Thus, you need to place the item to the left of the expression that will most likely fail in AND ( continuous range ) and to the left side that will most likely succeed in OR ( discrete ranges ).

 Even though there are may different ways to solve any problem, you still need to design its logic before beginning coding.  It is an art and a science to take an equation and turn it into an algorithm that someone can implement in code.  Design is the communication channel for those designing the algorithm ( highly educated engineers ) and those implementing the design ( trained coders ).

The design does not have to include the variable declarations since not every programming language is strongly typed language like C++ and Java is, but including variable declarations is not an error.  Header structure, libraries used, in-code comments, are never show up in program design.  Design is thee to guide the algorithm development, not the programming process.

// This program adds values from start to end one step at a time
//Author: Zoltan Szabo
//Version 1.0.0
#include <iostream>
 
using namespace std;
 
int main() {
 int start, end, sum = 0, count;
 
 do {                                     //validates to make sure user types in a positive value
  cout << "Enter a starting point: ";
  cin >> start;
 } while (start<0);
 
 do {                                     //validates to make sure the user types in larger value than the starting point
  cout << "Enter the ending point: ";
  cin >> end;
 } while (end<start);
 
 for (count = start; count <= end; count++) {
  sum += count;                         //accumulator to hold the sum
 }
 
 cout << "The sum of the values from " << start << " to " << end << " is " << sum << "." << endl;
 return 0;
} 

Java implementation of the same design might also include other use input validation by handling exceptions that would also not show up in the design of the methods.  Java also is a language that makes generating documentation much easier by the inclusion of docstrings that is up to the programmer to implement.

import java.util.Scanner;
/**
* The description for the class should describe the purpose of the class
* @author Zoltan Szabo
* @version 1.0.0
*/
public class SigmaStartEnd {
  /**
  * Every method needs description as well to help understand the purpose of the method
  * @param args Array of command line arguments
  * @return nothing
  * @throws In this case the method does not throw any exceptions
  */
  public static void main(String args[]) {
 Scanner keyboard = new Scanner(System.in);
 int start = 0, end = 0, sum = 0, count;
 try {
    do {     //validates to make sure user types in a positive value
  System.out.print("Enter a stating point: ");
  start = keyboard.nextInt();
    } while (start<0);
 
    do {    //validates to make sure the user types in larger value than the starting point
  System.out.print("Enter the ending point: ");
  end = keyboard.nextInt();
    } while (end<start);
 
    for (count = start; count <= end; count++) {
  sum += count;                         //accumulator to hold the sum
    }
 }
 catch (java.util.InputMismatchException e) {
    System.out.print("The value you entered was not a number. Bye.");
    System.exit(1);
 }
 System.out.print("The sum of the values from " + start + " to " + end + " is " + sum + "."); 

        keyboard.close();

   }// end of method
}// end of class

It does not matter which one you use, flowchart or pseudocode either one can help you analyze and understand code that was not written by you.  Since design is language independent, any code can be turned into design and into another language implemented code.

File Download ( full resolution ) 

Any code that is increased in complexity is better to manage if it is broken into functions.  Functions are essential management features and they also allow for code re-usability.  Function designs are lesser known features of designs since based on the implementing language, it might need to be noted is the function is being called by value or by reference.  There is no international standard how to design function calls, but this implementation is what I prefer to show reference based parameters. This should be carefully considered based on the programming language chosen for the implementation since object oriented programming languages might like Java might not distinguish the type of calls.

File Download ( full resolution )