Recursion

Recursion (in programming) is when a method calls itself. Classic example - the factorial function.

n! = 1*2*3*...*(n-1)*n

Recursive definition: f(n) =

• 1, if n=0
• n*f(n-1), else

As a Java method:

public static int recursiveFactorial(int n){
   if (n==0) return 1;
   else return n*recursiveFactorial(n-1);
}

Values of the input variables for which we perform no recursive calls are called base cases (there should be at least one base case). Every possible chain of recursive calls must eventually reach a base case.

Calls to current method. Each recursive call should be defined so that it makes progress towards a base case.