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.

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:

Run Pause setup() draw()

Sketch #10 state: Loading...

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

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:

Run Pause setup() draw()

Sketch #11 state: Loading...