Recursive Algorithms

Recursion allows a problem to be broken down into sub-problems, defining a problem in terms of itself. Recursive methods work by calling themselves. As an example, take the factorial function:

In java, this can be written:

public static int factorial(int n){
if(n == 0) return 1;
return n * factorial(n-1);
}


Recursive algorithms have:

• A base case
• This is the case where the method doesn't call itself, and the stack begins to unwind
• Every possible chain of recursive calls must reach a base case
• If not the method will recurse infinitely and cause an error
• A recursive case
• Calls the current method again
• Should always eventually end up on a base case

Binary search is a recursively defined searching algorithm, which works by splitting an array in half at each step. Note that for binary search, the array must already be ordered.

Three cases:

• If the target equals data[midpoint] then the target has been found
• This is the base case
• If the target is less than data[midpoint] then we binary search everything to the left of the midpoint
• If the target is greater than data[midpoint] then we binary search everything to the right of the midpoint

public static boolean binarySearch(int[] data, int target, int left, int right){
if (left > right)
return false;
int mid = (left + right) / 2;
if(target == data[mid])
return true;
else if (target < data[mid])
return binarySearch(data,target,low,mid-1);
else
return binarySearch(data,target,mid+1,high);

}


Binary search has , as the size of the data being processed halves at each recursive call. After the call, the size of the data is at most .

Linear Recursion

• The method only makes one recursive call
• There may be multiple possible recursive calls, but only one should ever be made (ie binary search)
• For example, a method used in computing powers by repeated squaring:

public static int pow(int x, int n){
if (n == 0) return 1;
if (n % 2 == 0){
y = pow(x,n/2);
return x * y * y;
}
y = pow(x,(n-1)/2);
return y * y;
}


Note how despite multiple cases, pow only ever calls itself once.

Binary Recursion

Binary recursive methods call themselves twice recursively. Fibonacci numbers are defined using binary recursion:

• = 0
public static int fib(int n){
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n-1) + fib(n-2);
}


This method calls itself twice, which isn't very efficient. It can end up having to compute the same result many many times. A better alternative is shown below, which uses linear recursion, and is therefore much much more efficient.

public static Pair<Integer,Integer> linearFib(int n){
if(k = 1) return new Pair(n,0);
Pair result = linearFib(n-1);
return new Pair(result.snd+1, result.fst);
}


Multiple Recursion

Multiple recursive algorithms call themselves recursively more than twice. These are generally very inefficient and should be avoided.