Sorting

• When programs model data, either internally or imported from a source such as a database, they often need to sort it. Some data structures are not ordered, meaning that elements are not arranged in consecutive order. For example, a program could contain an array with text strings inside it. To sort the array so that the text strings are arranged in ascending order alphabetically, the program may need to use an algorithm. Merge sort is an example of a recursive method for this process. Merge sort works by continually dividing the array into two, sorting each half before merging them back into one.
  
  

Searching

• When programs store data in data structures, they often need to locate particular elements using searching algorithms, which can benefit from recursion. For example, if an array is storing values in alphabetical order, the program may use recursion to figure out what position a certain element is at. Binary search involves the program continually checking an element midway through the array. If the element matches the one the program is looking for, it can stop. If it is not the element in question, the algorithm can check whether it is greater or less than the search element. If it is greater, the algorithm can eliminate the upper half of the structure beyond the current element, as the search element must be in the lower half. This process continues until the element is located.
  
  

Data Structures

• When deciding on algorithms, programmers should ask whether an iterative function that is not recursive could solve the task as well as a recursive one. For example, in certain data structures, a program will need to search through in a linear fashion until it locates a search item. In this case there is no alternative but to iterate through the structure. Recursive algorithms simplify the task with each iteration, checking to see if the end point has arrived, then calling the function again if it has not. To demonstrate the similarities between recursion and iteration, the following sample Java method shows a recursive method outline:
  public void processNumber(int myNum) {
  if(myNum>100) return;
  else processNumber(myNum*5);
  }
  
  An alternative iterative implementation of this would be as follows:
  int aNum=3;
  while(aNum<100) { aNum*=5; }
  
  In this case the iterative version is simpler.
  
  

Mathematical Tasks

• Some mathematical processing tasks are particularly well suited to recursive functions. Fibonacci sequences demonstrate recursive processing. Each number in a Fibonacci sequence is the sum of the previous two. The following sample Java code demonstrates a function to find a Fibonacci number:
  public int getFibonacci(int fNum) {
  if(fNum<=1) return fNum;
  else return getFibonacci(fNum-1) + getFibonacci(fNum-2);
  }
  
  The method returns the number in the Fibonacci sequence at the position indicated by an integer parameter when the code calls it, as follows:
  getFibonacci(8);
  
  This would return the eighth number. (See References 3, 4, 5)