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.