Recursion

Factorial

Factorial(n), usually denoted n!, is the product of all positive integers less than or equal to n. for example:

5! = 5 * 4 * 3 * 2 * 1 = 120

Consider the iterative function for factorial

int factorial(int n) {
	int fact = 1;
	for(int i=n; i>0; i--) {
		fact *= i;
	} 
	return fact;
}

There is another approach to writing this factorial code, one using recursion.

To write that recursion you need two intuitions: a base case and a recursion. For factorial, these are:

1. 0! = 1 (base case)
2. n! = n * (n-1)! (recursion)

We can now rewrite the function recursively

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

Sorted Search

It is never necessary to use recursion, you can always rewrite your function iteratively. Writing recursively sometimes helps us see a better solution. Consider trying to find an item in the following sorted list:

[2, 4, 9, 22, 45, 90, 192]

Is 200 in this list? To find this out, you might search through the list from beginning to end looking for 200. It would look like this:

boolean search(int[] arr, int n) {
	for(int i : arr) {
		if(i==n) return true;
	}
	return false;
}

However, you could also consider another algorithm which would complete faster:

Search through arr for n: 1. if the middle item in the array is n, return true (base case) 2. if the array is one item or smaller, return false (base case) 3. search through the approriate half of the array (recursion)

Here is that algorithm in java:

boolean search(int[] arr, int n) {
	int mid = arr[arr.length/2];
	if(mid==n) return true;
	if(arr.length<=1) return false;
	if(n>mid) return search(secondhalf(arr), n);
	return search(firsthalf(arr), n);
}

Tools

vim power user guide

I recommend putting the following into your ~/.vimrc file

set number
set shiftwidth=2
set tabstop=2
set smarttab
set smartindent
set autoindent
syntax on

Assignment

Recursion Functions