Wednesday, December 24, 2008

Recursive algos

Few recursive algos:


function factorial(int n)
  if ( n==0 ) return 1;
  else return n*factorial(n-1);

Fibonacci numbers:

function fibo(int n)
  if( (n==0) || (n==1) ) return 1;
  else return fibo(n-1)+fibo(n-2);

Greatest common divisor of 2 numbers :

function gcd(int x, int y)
  if(y == 0) return x;
  else return gcd(y, x%y);

Tower of Hanoi: Given 3 pegs, one with a set of N disks of increasing size, determine the minimal/optimal no of steps required to move the disks from their initial position to another peg without placing a larger disk on top of a smaller one

function hanoi(int n)
  if(n==1) return 1;
  else return 2*hanoi(n-1)+1;

Binary search : Search an ordered array of elements by cutting the array in half on each pass

function binary_search(int* data, int tofind, int start, int end)
  int mid = start + (end-start)/2; // no float/double
  if(start > end)
    return -1;
  else if(data[mid] == tofind)
    return mid;
  else if(data[mid] > tofind)
    return binary_search(data, tofind, start, mid-1);
    return binary_search(data, tofind, mid+1, end);

No comments: