Recursion

Recursive Function#

• A function that calls itself
• Solves problems by solving smaller instances of the same problem until the problem is so small it can be solved directly
• (also see Recursive Function )

Russian Doll#

A russian doll is a good example of recursion, as it gets smaller and smaller until there exists a doll that is too small to contain another doll

Parts to a Recursive Function#

1. A simply case: can be solved directly
2. A complex case: can be made simpler (and simpler … until it looks like the simple case)

Factorial#

Find the factorial of n using recursion

• Analysis:
  • a factorial of n can be thought of as n * (n-1)!
  • a factorial of (n-1) can be thought of as (n-1) * (n-2)!
  • and so on, until n == 0, because 0! == 1

Java Code Below:

public static int factorial(int n){
    // base case
    if(n == 0){
        return 1;
    }

    // recursive calls
    return n * factorial(n-1);
}

Fibonacci Sequence#

Find the nth number in the Fibonacci Sequence using recursion

• Analysis:
  • a fibonacci num of n is the sum of the (fibonacci num of n-1) + (fibonacci num of n-2)
  • a fibonacci num of n-1 is the sum of the
    (fibonacci num of (n-1)-1) + (fibonacci num of (n-1)-2)
  • and so on, until you reach 0 or 1 (the two starting numbers of the sequence)

Java Code Below:

public static int fibonacci(int n){
    // 2 base cases
    if(n == 0){
        return 0;
    }
    if(n == 1){
        return 1;
    }

    // prints which fibonacci value we're computing
    System.out.printf("computing fibonacci(%d)\n", n);     
    
    // recursive calls
    return fibonacci(n-1) + fibonacci(n-2);
}

Output of fibonacci(5):

computing fibonacci(5)
computing fibonacci(4)
computing fibonacci(3)
computing fibonacci(2)
computing fibonacci(2)
computing fibonacci(3)
computing fibonacci(2)
5

Memoization#

You should notice that we’re calculating the same fibonacci number multiple times, which is unnecessary and uses space and time. To counter this, we use a process called Memoization

In order to memoize our algorithm, we can implement a HashMap to store the calculated fibonacci numbers.

Java Code Below:

// using memoization:
// when recursing, we're actually calculating the same value
// multiple times, wasting space & time
// to see a visual of the fibonacci sequence with and
// without memoization, visit https://recursion.now.sh/  
// and choose fibonacci from the "Pre-defined templates", 
// then run fn(5) with "Enable memoization" off
// then run fn(5) again but with "Enable memoization" on
// you should notice that with "Enable memoization" on there
// are no repetitions and the function is faster


// initialize a HashMap which stores keys and values that 
// correspond to the keys (rough explanation)
public static Map<Integer, Integer> memo = new HashMap<>();

public static int fibonacci(int n){
    // 2 base cases
    if(n == 0){
        return 0;
    }
    if(n == 1){
        return 1;
    }

    // if the HashMap contains the key n already,
    // return the value stored w/ the key
    if(memo.containsKey(n)){
        // prints which memo value we're grabbing
        System.out.printf("grabbing memo[%d]\n", n);        
        // grab the value
        return memo.get(n);                                 
    }

    // recursive calls
    // prints which fibonacci value we're computing 
    System.out.printf("computing fibonacci(%d)\n", n);  
    // compute the fibonacci value (using recursion)
    // and store it into result
    int result = fibonacci(n-1) + fibonacci(n-2);       

    // store the value result with the key n
    memo.put(n, result);     
    // return result                           
    return result;                                      
}

Output of fibonacci(5):

computing fibonacci(5)
computing fibonacci(4)
computing fibonacci(3)
computing fibonacci(2)
grabbing memo[2]
grabbing memo[3]
5

Notice the lack of repetition and unnecessary calculation, giving us a more optimal solution

Stack Overflow#

If you ever encounter a “stack overflow” error, 99% of the time it’s because of an infinite recursion or too many recursive function calls.

Check out this article for more on stack overflow errors.

Check out this demo and this demo for visual representations of recursive programs.

Created By: WHS Comp Sci Club Officers