Introduction

I find recursion to be one of the most important and awesome programming techniques. It's extremely useful and makes some kind of problems (that seems very difficult) easy!
Also the recursive solution tends to be shorter (not always), easer to read or understand. But implementing recursion is space consuming and slower than the iterative counterpart!

Definition

recursion is:
if you got it, stop else please see recursion definition.

The idea of recursion comes from math which btw I think it can be consider to be the same science than Computer.
A recursive algorithm is an algorithm that calls it self. This is, an algorithm that in it definition includes it self. At the beginning this can sound stupid or incomplete but it's a very powerful technique!

Here's our first example (in Java):
An algorithm that for a given number, returns true if the number is even, false if it is odd. The number must be >= 0.

/*
 * Seudocode:
 * Taking advantage of the fact that even and odds numbers are alternated,
 * we can say that a number is even if the previous number
 * is odd and a number is odd if the previous number is even.
 * We need a point where to stop recursion otherwise we will loop forever!
 * Our stop case can be the number zero which we know is even. 
 * Therefore the seudocode can be:
 * if the number is zero, return true. (this is the base case)
 * otherwise return the negation of isEven(number-1). (this is the recursive call that
 * must get us closer to the base case)
 * 
 */	
 public static boolean isEven(int num) {
	 return (num==0) || !isEven(num-1);
 }
Note that implementing this iteratively would be faster and smaller!
public static boolean isEven(int num) {
	return (num%2==0);
}
But this is more an exception that the common case!
Let's go with the well know factorial example: Factorial(n) is 1 if n=0, is n * Factorial(n-1) if n > 0.

Recursive:
public static long factorial(int num) {
	return (num==0)?1L:num*factorial(num-1);
}
NonRecursive:
public static long factorial(int num) {

	long factorial= 1;

	while(num>1){
		factorial*= num--;
	}

	return factorial;
}
Here the recursive solution is easer to read but it will consume more time and space to run!