## 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.