## Jupyter at Bryn Mawr College

Public notebooks: /services/public/dblank / CS110 Intro to Computing / 2015-Fall / 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 [13]:
int factorial(int n) {
if (n == 1)
return 1;
else
return factorial(n - 1) * n;
}

int line = 20;

void printLine(String str) {
fill(0);
text(str, 10, line);
line += 15;
}

void setup() {
size(500, 100);
printLine("factorial(5): " + factorial(5));
printLine("factorial(6): " + factorial(6));
}

Sketch #10:

## 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 [14]:
int fib(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 1;
}
return fib(n - 1) + fib(n - 2);
}

int line = 20;

void printLine(String str) {
fill(0);
text(str, 10, line);
line += 15;
}

void setup() {
size(500, 100);
printLine("fib(3): " + fib(3));
printLine("fib(4): " + fib(4));
printLine("fib(5): " + fib(5));
printLine("fib(6): " + fib(6));
}

Sketch #11: