As usual, this is not a comprehensive review sheet, nor is it "official."

## Linked Lists

### Accessing parts of a list with `first`

and `rest`

Recall that given any list, we can use `first`

and `rest`

to access its head and remainder, respectively:

```
(define my-list (list 1 true "hello" 50))
(first my-list) ; 1
(rest my-list) ; (list true "hello" 50)
```

### Lists as `cons`

pairs

Until now, you've been using lists as one-dimensional data structures:

`(list 1 2 3)`

It turns out that this `list`

constructor function is just a convenient wrapper over the real structure of a list.

We use `cons`

to build lists out of **pairs**, attaching a new item to an existing list:

```
; (list 1 2 3) is equivalent to
(cons 1
(cons 2
(cons 3 empty)))
; a single-element list
(cons 3 empty)
```

So lists are actually *nested pairs* like this:

```
+-----+-------------------------+
| |-----+-----------------+ |
| | |-----+---------+ | |
| 1 | 2 | 3 | empty | | |
| | |-----+---------+ | |
| |-----+-----------------+ |
+-----+-------------------------+
first rest
```

Formally, a **List-of-X** is one of:

`empty`

`(cons X List-of-X)`

Note that this is a

recursivedefinition. A recursive definition uses the term being defined (in this case,`List-of-X`

) within its definition (in this case, it's used in the second line,`(cons x List-of-X)`

).

## Recursion

Since lists are recursive data structures, we can use recursive procedures to perform operations on them.

In general, a recursive procedure follows the structure

```
(if <Base Case> ; determined by the input type
<Base Case Result> ; determined by the output type
(<Combine> <Current Data> <Recursive Call with Remainder Data>))
```

Breaking things down further, the recursive call typically involves the following steps:

- Break the data into a "current" piece and a "remainder"
**Handle**the "current" piece according to the function**Recursively call your function**with the "remainder" of the data**Combine**the results from 1 and 2, and return this combination

### Avoiding infinite loops

It is extremely important that your recursive call uses a *smaller* version of the original input data. Otherwise, you'll never reach your base case, and the function will recurse forever.

The following function loops forever:

```
; factorial/broken : number -> number
(define (factorial/broken n)
(if (= n 0) 1 ; remember that 0! = 1 by definition
(* n
(factorial/broken n)))) ; eek
```

Once we fix our recursive call to operate on `(- n 1)`

, it works:

```
; factorial : number -> number
(define (factorial n)
(if (= n 0) 1
(* n
(factorial (- n 1))))) ; much better
```

### Base Cases

Here are some common base cases and combinations:

Type | Base Cases | Splitters | Combiners |
---|---|---|---|

Number | `0` , `1` |
`-` |
Arithmetic operations (usually `+` or `*` ), `max` and `min` |

String | `""` |
`substring` |
`string-append` |

List | `empty` |
`first` and `rest` |
`cons` , (less frequently) `append` |

Image | `empty-image` |
N/A (usually a return type) | `overlay` and variants |

### Examples of templates for recursion

These are all very general templates; you will almost never be able to follow them exactly, so memorizing them won't do you much good. However, they do provide examples of the base cases.

Note that the `<Base Case Result>`

and `<Combiner>`

depend on the output type, which is specified as `X`

in all of the examples below.

#### Lists

```
; List -> X
(define (recursive-lst-proc lst)
(if (empty? lst) <Base Case Result>
(<Combiner> (first lst)
(recursive-lst-proc (rest lst)))))
```

#### Numbers

```
; Number -> X
(define (recursive-num-proc n)
(if (= n 0) <Base Case Result>
(<Combiner> n
(recursive-num-proc (- n 1)))))
```

#### Trees

```
; Tree -> X
(define-struct node (value children))
(define (recursive-tree-proc t)
(if (empty? t) <Base Case Result>
(<Combiner> (node-value t)
(map recursive-tree-proc (node-children t)))))
```

## Iterative Recursion

**Iterative recursion** is also called **recursion with accumulators** (and infrequently in this course, **tail recursion**).

The main difference between "ordinary" recursion and iterative recursion is that iterative recursion uses an **accumulator** as an additional input to the function.

This accumulator represents the "partial result" of the computation at the current position in the data. It allows the computer to represent the previously-seen data in a compact manner, by only remembering the "relevant" parts. (What's relevant is determined by the particular task of the function -- here are some examples:)

Input | Task | Accumulator |
---|---|---|

List of numbers | Sum | Partial sum of all numbers seen so far |

List of strings | Longest string | Longest string seen so far |

List of numbers | List of all odd numbers | List of all odd numbers seen so far |

Here are two version of `sum-list`

, written without and with accumulators.

```
; sum-list : List-of-Number -> Number
(define (sum-list lon)
(if (empty? lon)
0
(+ (first lon)
(sum-list (rest lon)))))
; sum-list/iter : List-of-Number -> Number
(define (sum-list/iter lon acc)
(if (empty? lon)
acc ; changed from 0
(sum-list/iter (rest lon)
(+ (first lon) acc)))) ; note that the (+ (first lon) ...) has been moved INSIDE the recursive call
```

Here's a comparison of how the two functions are evaluated:

```
; Without accumulator
(sum-list (list 1 2 3 4))
; With accumulator
(sum-list/iter (list 1 2 3 4)
0)
```

After one time step:

```
; Without accumulator
(+ 1
(sum-list (list 2 3 4)))
; With accumulator
(sum-list/iter (list 2 3 4)
1)
```

After another step:

```
; Without accumulator: notice the "trail" growing...
(+ 1
(+ 2
(sum-list (list 3 4))))
; With accumulator: still nice and compact
(sum-list/iter (list 3 4)
3)
```

```
; Without accumulator
(+ 1
(+ 2
(+ 3
(sum-list (list 4)))))
; With accumulator
(sum-list/iter (list 4)
6)
```

```
; Without accumulator
(+ 1
(+ 2
(+ 3
(+ 4
(sum-list empty)))))
; With accumulator
(sum-list/iter empty
10)
```

```
; Without accumulator
(+ 1
(+ 2
(+ 3
(+ 4
empty))))
; With accumulator
10
```

Evidently, iterative recursion is *far more efficient* than regular recursion. That's because the accumulator is basically a *compact encoding of everything the program needs to know about the previously-seen data*, so we don't need to remember all the data itself.

## Imperative Programming

**Imperative programming** is a style of programming characterized by providing the computer simple, detailed instructions for everything.

Functional | Imperative |
---|---|

Functions almost always take inputs |
Functions may not take any inputs |

Functions always have return values |
Functions may not have any return value (i.e. they may return `void` ) |

Functions always return the same output for a particular input |
Functions are allowed to return whatever they want, or nothing at all |

Use recursion to traverse structures |
Use iteration to traverse structures |

Variables never change values (they are "immutable") |
Variables can change values (they are "mutable") |

Functions never affect things outside their scope |
Functions have "side effects" |

Here are the main imperative functions you should understand:

### Do nothing

`(void)`

Does nothing. If a function doesn't return any values, we say it "returns `(void)`

".

### Conditionally do nothing

```
(when <Condition> <Result>)
(unless <Condition> <Result>)
```

`when`

executes `<Result>`

if and only if `<Condition>`

is true. `unless`

does the opposite.

Fun fact:the funnest fact.`; (when <Condition> <Result>) is equivalent to (if <Condition> <Result> (void)) ; (unless <Condition> <Result>) is equivalent to (if <Condition> (void) <Result>)`

### Do a sequence of instructions

```
(begin
<FunctionCall#1>
<FunctionCall#2>
...
<ReturnFunctionCall>)
```

Executes a sequence of function calls, one at a time, and returns the value of the last one.

### Mutate variables

`(set! <Variable Name> <New Value>)`

Note that `<Variable Name>`

must previously have been `defined`

.

### Iteratively traverse a list

```
(for-each proc lst)
; if lst is a List-of-X, then proc must take an input of type X
```

Just like `map`

, in that it calls `proc`

with each item in order, but *does not* return the resulting list.

Warning:Remember to use`for-each`

with a`proc`

that performs some kind of mutation (or causes a side effect). If`proc`

just returns a new value, that value will disappear into the void, since`for-each`

doesn't return anything.`(define my-list (list 1 2 3)) (define (doubler n) (* 2 n)) (for-each doubler my-list) ; my-list is still (list 1 2 3)`

### What you should know

Understand how side effects work, and how to translate functional-style code into its imperative equivalents.

Here's an example: the inimitable `sum-list`

, written imperatively, with and without `for-each`

.

```
; sum-list/imperative : (listof number) -> number
; sums a list imperatively
(define (sum-list/imperative lon)
(local [(define sum 0)
(define remaining lon)
(define (loop)
(if
; If remaining is an empty list, return sum
(empty? remaining) sum
; Otherwise...
(begin
; First, update the value of sum
(set! sum (+ sum (first remaining)))
; Next, update the remaining list
(set! remaining (rest remaining))
; Finally, repeat
(loop))))]
; Kick off the loop
(loop)))
; sum-list/for-each : (listof numbers) -> number
; sums a list imperatively
(define (sum-list/for-each lon)
(local [; Initialize the sum to zero
(define sum 0)]
(begin
; Loop through the list, adding each item to the sum
(for-each (lambda (item)
(set! sum (+ sum item)))
lon)
; After we're done looping, return the sum
sum)))
; Using for-each works the same way as before
(check-expect (sum-list/for-each (list 1 2 3))
(sum-list (list 1 2 3)))
```

## Structs and mutation

Recall that structs have "accessor" functions for each of their fields:

`(<Struct Name>-<Field Name> <Instance of Struct>)`

```
(define-struct person (name age))
; name is a string
; age is a number
(define wizard (make-struct "Harry Potter" 17))
(person-name wizard) ; "Harry Potter"
```

Just as we can use `set!`

to mutate previously-defined variables, we can *mutate the fields of structs*.

`(set-<Struct Name>-<Field-Name>! <Instance of Struct> <New Field Value>)`

```
; Continuing the above example...
(person-name wizard) ; "Harry Potter"
(set-person-name! wizard "Ron Weasley")
(person-name wizard) ; "Ron Weasley"
```

## What else?

Things that might be helpful to brush up on:

- Type signatures and consistency (this will never
*not*be important) - Grammar rules of Racket
- Local scope (
`local`

) - Basics of how structs work

Ways to evaluate your preparedness:

Can you do all of the homeworks/tutorials since the last midterm?

- Not because we're going to pop some wild evolutionary tree question on you, but because they're good applications of the course material (and good examples of how we write questions!)

Can you write your own implementations of

`map`

,`filter`

,`foldl`

,`ormap`

, etc. using both recursion and imperative iteration?