Building Linked Lists Recursively

Building Lists Recursively

We can write functions that take in any assortment of parameters, including Lists, that return a brand new List!

Basic Steps: The following steps are general guidelines for how to approach designing a recursive List-building function.

1. Determine what your base case is. Under what condition will you return null and stop recurring?

2. Process the first value of your new List

3. cons it onto the result of a recursive call that will process the rest of your list.

Examples:

First, let's look at some examples that may be familiar to you from lecture!

1. acronimify

This function takes in a List of strings, and returns back a List of strings that consists of only the first letters of the strings in the initial List. To extract the first letters we make use of the substring method. Within the function we have highlighted which lines of code match up to each basic step of recursive List building.

let acronymify = (words: Node<string>): Node<string> => { 
   // 1. Base case
   if (words === null) {         
       return null;    
   } else {        
       let letter: string = first(words).substr(0, 1); // 2. Process first value        
       return cons(letter, acronymify(rest(words))); // 3. cons to rest of the new List you're building!    
   }
};

export let main = async () => {    
    let ex1: Node<string> = listify("apple", "banana", "clementine");    
    let acronym1: Node<string> = acronimify(ex1);    
    print(acronym1);
};

a --> b --> c --> null will be printed on your screen.

2. bounceList

This function takes in two Lists of strings. The first one is the List of names currently "in line" and the second List is the "blacklist" or List of names to be omitted from the final List that is returned.

let bounceList = (line: Node<string>, banned: Node<string>): Node<string> => {    
    // 1. base Case
    if (line === null) {        
        return null;    
    } else {        
        let person: string = first(line); // 2. Process first value         
        if (includes(banned, person)) {                
            return bounceList(rest(line), banned);         
        } else {                
        // 3. cons to rest of the new List you're building!                
            return cons(person, bounceList(rest(line), banned));          
        }     
    }
};
let includes = (list: Node<string>, search: string): boolean => {    
    if (list === null) {        
        return false;    
    } else {        
        if (first(list) === search) {            
            return true;        
        } else {           
            return includes(rest(list), search);        
        }    
    }
};

export let main = async () => {    
    let animals: Node<string> = listify("lion", "tiger", "bear");    
    let notCats: Node<string> = listify("bear");    
    let cats: Node<string> = bounceList(animals, notCats);    
    print(cats);
};

The output will be lion --> tiger --> null. While this function is more complicated than acronimify and makes use of a helper function includes, it still hits each of the three basic steps for recursive List building. However, note that in this case step 3 may not be executed in each recursive call -- we only want to add an item to our new list if it meets a certain criteria.

3. squareMe

This last example function is going to be slightly different than the previous two -- steps 2 & 3 are going to be combined into one line.

let squareMe = (initial: Node<number>): Node<number> => { 
        // 1. Base case
        if (initial === null) {        
            return null;     
        } else {        
        // 2. & 3. Process first value AND cons onto rest of list        
          return cons((first(initial) ** 2), squareMe(rest(initial));   
        }
};

export let main = async () => {    
    let x: Node<number> = cons(1, cons(2, cons(3, null)));    
    let y: Node<number> = squareMe(x);    
    print(y);
};

Output will be 1 --> 4 --> 9 --> null. The first argument in our call of the cons function is where we process the first value of our list to be added. We can simply pass in the expression for calculating the square of the first number in as an argument. Alternatively we could create a variable to hold the result of this expression, but it's important to be able to recognize the steps in a recursive function even when they present themselves in slightly different ways.

Comp 110 Building Linked Lists Recursively

Building Lists Recursively

Examples: