# Recursion

## Steps in drawing out the recursive call.

How to write a method that calls itself. https://www.youtube.com/watch?v=MyzFdthuUcA – Dave Feinberg’s video series.

1. Write “if”.
There must be at least 2 cases:, a recursive case (where the method calls itself) and a base case (where the method does not).
2. Handle the simplest case(s). “Base Case”
Simplest = no recursive call needed (no further loop)
3. Write the recursive call(s).
On the next simpler input/state, it may help to store the recursive call
4. Assume the recursive call works .
Ask yourself: What does it do?
Ask yourself: How does it help?

## Factorial

### Base Case

If n! is defined as the product of all positive integers from 1 to n, then:
1! = 1*1 = 1
2! = 1*2 = 2
3! = 1*2*3 = 6
4! = 1*2*3*4 = 24

n! = 1*2*3*…*(n-2)*(n-1)*n
and so on.
Logically, n! can also be expressed n*(n-1)! .

Therefore, at n=1, using n! = n*(n-1)!
1! = 1*0!
which simplifies to 1 = 0!

### Java Recursive Factorial Method

```// precondition: n >= 0
public static in fact(int n) {
if (n=0) return 1;
else return fact(n-1) * n;
}

```
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}