## Jupyter at Bryn Mawr College

Public notebooks: /services/public/dblank / CS110 Intro to Computing / 2017-Spring / Notes

# Recursion¶

Defining something in terms of itself.

"You can't do that!" - Mom

Yes, you can.

## Factorial¶

factorial of $5 = 5 * 4 * 3 * 2 * 1$

• The factorial of 1 is 1.
• The factorial of n is the factorial(n - 1) * n.
In [10]:
int factorial(int n) {
if (n == 1)
return 1;
else
return factorial(n - 1) * n;
}

void setup() {
for (int i = 1; i < 11; i++) {
println("factorial(" + i + "): " + factorial(i));
}
}

Sketch #10:

factorial(1): 1
factorial(2): 2
factorial(3): 6
factorial(4): 24
factorial(5): 120
factorial(6): 720
factorial(7): 5040
factorial(8): 40320
factorial(9): 362880
factorial(10): 3628800


## Fibonacci¶

Fibonacci sequence: 1 1 2 3 5 8 13

• The fib of 1 is 1.
• The fib of 2 is 1.
• The fib of n is the fib(n - 1) + fib(n - 2).
In [6]:
int fib(int n) {
if (n == 1) {
return 1;
} else if (n == 2) {
return 1;
} else {
return fib(n - 1) + fib(n - 2);
}
}

void setup() {
println("fib(3): " + fib(3));
println("fib(4): " + fib(4));
println("fib(5): " + fib(5));
println("fib(6): " + fib(6));
}

Sketch #6:

fib(3): 2