Recursion

Factorial

int Factorial (int num)
{
	if (num == 0)
		return 1;
	else
		return num * Factorial (num - 1);
}
		

Power

int Power (int base, int exponent)
{
	if (exponent == 1)
		return base;
	else
		return base * Power (base, exponent - 1);
}
		

Fibonacci Number

Fibonacci Sequence
1, 1, 2, 3, 5, 8, 13, 21, 43, ...

int Fibonacci (int n)
{
	if (n <= 2)
		return n;
	else
		return Fibonacci (n - 1) + Fibonacci (n - 2);
}
		

Largest element in an Array

int Largest (const int list[], int lowerIndex, int upperIndex)
{
	int max;

	if (lowerIndex == upperIndex)	// size of list is one
		return list[lowerIndex];
	else
	{
		max = Largest (list, lowerIndex + 1, upperIndex);

		if (list[lowerIndex] >= max)
			return list[lowerIndex];
		else
			return max;
	}
}
		

Convert Decimal to Binary

void DecToBin (int num, int base)
{
	if (num > 0)
	{
		DecToBin (num / base, base);
		cout<<num % base;
	}
}
		

Print a Linked List in a Reverse Order

template <class Type>
void linkedListType<Type>::printReverse () const
{
	reversePrint (first);
	cout<<endl;
}

template <class Type>
void linkedListType<Type>::reversePrint (nodeType<Type>* current) const
{
	if (current != NULL)
	{
		reversePrint (current->link);
		cout<<current->info<<" ";
	}
}
		

Search for an element in a Linked List

template <class Type>
bool linkedListType<Type>::Search (nodeType<Type>* current, Type item) const
{
	if (current == NULL)
		return false;
	else if (current->info == item)
		return true;
	else 
		return Search (current->link, item);
}
		

Tower of Hanoi

  1. Only one disk can be moved at a time.
  2. The removed disk must be placed on one of the needles.
  3. A larger disk can not be placed on top of a smaller disk.
void MoveDisks (int count, int needle1, int needle3, int needle2)
{
	if (count > 0)
	{
		MoveDisks (count - 1, needle1, needle2, needle3);

		cout<<"Move disk "<<count<<" from "<<needle1
			<<" to "<<needle3<<"."<<endl;

		MoveDisks (count - 1, needle2, needle3, needle1);
	}
}