So far we’ve used recursion to recursively define a set of steps to solve a problem. This week, we’ll switch our focus to doing the same sort of thing for data structures.

What really are lists? Now that we see how iteration is just recursion…what does it truly mean to have a “list” of data? Specifically, we’ll focus on how them being “inductively defined” is what makes our recursive algorithms so convenient. Essentially, last week we spent building recursive algorithms to “process” or “destroy” data and this week we’re going build recursive data structures!

The way we store data in our programs affects the way we can use it! By inductively defining a data structure, it gives us insight on how to traverse it using recursion. For example, we’ll see the following data definition for lists:

; a list is either :
;   - '() ; the empty list
;   - (cons something list) ; a pair of an element and a list: 

In-Class Resources