Recursive algos

Few recursive algos:

Factorial:

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);
  else
    return binary_search(data, tofind, mid+1, end);
}