Recursion
See Google's definition of recursion. LOL.
It has a lot to do with factorials. How to write x! as a routine in Java?
int fact(int x) {
int f = 1;
for (int i = 2; i <= x; i++) {
f *= i;
}
return f;
}
Fibonacci: F(n) = F(n-1) + F(n-2)
/* WARNING: this is REALLY slow. Lots of repeated calls.
This is super-duper slow. */
public static int fibonacci(int n)
{
if (n <= 2) return 1;
return fibonacci(n-1) + fibonacci(n-2);
}
Displaying a number as words
public static void displayAsWords(int number)
{
if (number < 10) { // number has 1 digit
System.out.print(getWordFromDigit(number) + " ");
}
else { // number has >1 digits
displayAsWords(number / 10);
System.out.print(getWordFromDigit(number%10) + " ");
}
}
Keys to successful recursion
- Must have an if-else statement or some other branching logic that leads to different cases depending on the function parameters.
- One or more of the branches must include no recursive calls in order to stop.
Recursion and the Call Stack
- a "Stack" is a place where local (primative) variables are stored.