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.

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:

Run Pause setup() draw()

Sketch #10 state: Loading...

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

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:

Run Pause setup() draw()

Sketch #6 state: Loading...

fib(3): 2
fib(4): 3
fib(5): 5
fib(6): 8
fib(3): 2
fib(4): 3
fib(5): 5
fib(6): 8