# Recursion

## Fork this

https://github.com/iloveponies/recursion

Here are the instructions if you need them. Be sure to fork the repository behind the link above.

## Recap

This chapter talks a lot about collections and we’ll need the functions `first`

and `rest`

:

```
(doc first)
(doc rest)
(first [1 2 3 4]) ;=> 1
(first '(1 2 3 4)) ;=> 1
(rest [1 2 3 4]) ;=> (2 3 4)
(rest '(1 2 3 4)) ;=> (2 3 4)
(rest [1]) ;=> ()
(rest []) ;=> ()
```

`first`

gives the first element of a sequence, and `rest`

gives all but the first element.

## Recursion

So far we’ve manipulated collections with functions like `map`

and `filter`

. How do they work? They are all based on *recursion*. Recursion is the low-level method of iteration found in functional languages. While the higher-level functions like `map`

are usually nicer to use than implementing the equivalent algorithm with recursion ourselves, there are often situations when the structure of the algorithm or the data it operates on is such that the existing higher-level functions do not quite work on it.

### Lists are recursive structures

Let’s look at the function `cons`

. It takes two parameters, a value and a sequence, and returns a new sequence with the value added to the front of the original sequence. For an example, to construct the sequence `(1 2 3 4)`

, we could write:

```
(cons 1
(cons 2
(cons 3
(cons 4 '()))))
;=> (1 2 3 4)
```

`'()`

is the empty sequence.

To process this nested structure suggests that we should first process the first element of the sequence, and then do the operation again on the rest of the sequence. This is actually the general structure of *linear recursion*. As a concrete example, let’s look at how to implement `sum`

.

```
(defn sum [coll]
(if (empty? coll)
0
(+ (first coll)
(sum (rest coll)))))
(sum [1 2 3 4]) ;=> 10
```

The *sum* of a sequence is:

- 0, if the sequence is empty, or
- the
*first*element of the sequence*added*to the*sum*of the*rest*of the sequence.

Imagine an arrow drawn from the second *sum* to the first *sum*. This is the recursive nature of the algorithm.

The call to `sum`

begins by inspecting `coll`

. If `coll`

is empty, `sum`

immediately returns 0. If `coll`

is not empty, `sum`

takes its first element and adds it to the sum of the rest of the elements of `coll`

. The value 0 is the base case of the algorithm, which determines when the calculation stops. If we did not have a base case, the calculation would continue infinitely.

### Exercise 1

Write the function `(product coll)`

that computes the product of a collection of values. The product of \(a\), \(b\) and \(c\) is \(a * b * c\).

```
(product []) ;=> 1 ; special case
(product [1 2 3]) ;=> 6
(product [1 2 3 4]) ;=> 24
(product [0 1 2]) ;=> 0
(product #{2 3 4}) ;=> 24 ; works for sets too!
```

To get a better grasp on what `sum`

does, let’s see how it’s evaluated.

```
(sum '(1 2 3 4))
= (sum (cons 1 (cons 2 (cons 3 (cons 4 '())))))
;=> (+ 1 (sum (cons 2 (cons 3 (cons 4 '())))))
;=> (+ 1 (+ 2 (sum (cons 3 (cons 4 '())))))
;=> (+ 1 (+ 2 (+ 3 (sum (cons 4 '())))))
;=> (+ 1 (+ 2 (+ 3 (+ 4 (sum '())))))
;=> (+ 1 (+ 2 (+ 3 (+ 4 0)))) ; (empty? '()) is true, so (sum '()) ;=> 0
;=> (+ 1 (+ 2 (+ 3 4)))
;=> (+ 1 (+ 2 7))
;=> (+ 1 9)
;=> 10
```

Note that we expanded the list `'(1 2 3 4)`

to its `cons`

form. If we take a closer look at that form and the line with comment above, we’ll see why:

```
(cons 1 (cons 2 (cons 3 (cons 4 '()))))
...
;=> (+ 1 (+ 2 (+ 3 (+ 4 0 ))))
```

We replaced the `cons`

operation in the recursive structure with `+`

and `'()`

with `0`

. That is, we transformed the data structure into a calculation with the same form but different result.

### Exercise 2

Write down the evaluation of`(product [1 2 4])`

like we did for `sum`

above. This exercise does not give any points and you do not need to return it.
From this we get the general template for linear recursion over collections:

```
(defn eats-coll [coll]
(if (empty? coll)
...
(... (first coll) ... (eats-coll (rest coll)))))
```

The first branch of the `if`

is the base case and determines the value of `eats-coll`

when given an empty collection. The second branch determines what operation to apply on the elements of the collection.

We call this kind of computation *linear* because the expression it constructs grows linearly with the size of input.

### Exercise 3

Write the function `(singleton? coll)`

which returns `true`

if the collection has only one element in it and `false`

otherwise. This is a very useful helper function in the remainder of this chapter.

Do not use `count`

as it can be expensive on long sequences. This function is not recursive.

```
(singleton? [1]) ;=> true
(singleton? #{2}) ;=> true
(singleton? []) ;=> false
(singleton? [1 2 3]) ;=> false
```

### Exercise 4

Write `(my-last a-seq)`

that computes the last element of a sequence.

```
(my-last []) ;=> nil
(my-last [1 2 3]) ;=> 3
(my-last [2 5]) ;=> 5
```

Hint: what is the base case here? How can you check if you’re there?
### Exercise 5

Write the function `(max-element a-seq)`

that computes returns the maximum element in `a-seq`

or `nil`

if `a-seq`

is empty?

You can use the function `(max a b)`

that returns the greater of `a`

and `b`

.

```
(max-element [2 4 1 4]) ;=> 4
(max-element [2]) ;=> 2
(max-element []) ;=> nil
```

### Exercise 6

Write the function `(seq-max seq-1 seq-2)`

that returns the longer one of `seq-1`

and `seq-2`

. This is a helper for the next exercise. You do not need to use recursion here. It is okay to use `count`

.

```
(seq-max [1] [1 2]) ;=> [1 2]
(seq-max [1 2] [3 4]) ;=> [3 4]
```

### Exercise 7

Write the function `(longest-sequence a-seq)`

that takes a sequence of sequences as a parameter and returns the longest one.

```
(longest-sequence [[1 2] [] [1 2 3]]) ;=> [1 2 3]
(longest-sequence [[1 2]]) ;=> [1 2]
(longest-sequence []) ;=> nil
```

### Saving the list

All the functions so far, `sum`

, `product`

and `last-element`

, transformed the list into a single value. This it not always the case with linear recursion. Our old friend `(map f a-seq)`

is a good example of this. Here is the definition for it:

```
(defn my-map [f a-seq]
(if (empty? a-seq)
a-seq
(cons (f (first a-seq))
(my-map f (rest a-seq)))))
```

See how nicely it fits in the general template for linear recursion? Only deviation from it is the extra parameter `f`

. It is function, that will become part of the operation that the recursion applies to the elements of the sequence. Here’s the evaluation:

```
(map inc [1 2 3])
;=> (cons (inc 1)
; (cons (inc 2)
; (cons (inc 3) '())))
;=> '(2 3 4)
```

So `map`

calls the function `f`

for every element of `a-seq`

and then re-constructs the sequence with `cons`

.

### Exercise 8

Implement the function `(my-filter pred? a-seq)`

that works just like the standard `filter`

. Don’t use `remove`

.

```
(my-filter odd? [1 2 3 4]) ;=> (1 3)
(my-filter (fn [x] (> x 9000)) [12 49 90 9001]) ;=> (9001)
(my-filter even? [1 3 5 7]) ;=> ()
```

### Stopping before the end

Sometimes you can find the answer before hitting the base case. For example, the following function checks if a sequence contains only numbers. If we find something that isn’t a number on the way through, we can immediately stop and return `false`

.

```
(defn only-numbers? [coll]
(cond
(empty? coll)
true ; the empty sequence contains only numbers
(number? (first coll))
(only-numbers? (rest coll)) ; we got a number, let's check the rest
:else
false)) ; it wasn't a number so we have our answer
```

Here the recursion stops if we hit the base case (empty collection) or if we find a non-number.

```
(only-numbers? [1 2 3 4]) ;=> true
(only-numbers? [1 2 :D 3 4]) ;=> false
```

Let’s have a closer look at the evaluation of the second line:

```
(only-numbers? [1 2 :D 3 4])
;=> (only-numbers? [2 :D 3 4]) ; (number? 1) => true, so we now need to check
; if all the rest are numbers.
;=> (only-numbers? [:D 3 4]) ; because (number? 2) ;=> true
;=> false ; because (number? :D) ;=> false
```

### Exercise 9

Write the function `(sequence-contains? elem a-seq)`

that returns `true`

if the given sequence contains the given value, otherwise `false`

.

```
(sequence-contains? 3 [1 2 3]) ;=> true
(sequence-contains? 3 [4 7 9]) ;=> false
(sequence-contains? :pony []) ;=> false
```

Hint: remember to stop searching when you find it.
### Exercise 10

Write the function `(my-take-while pred? a-seq)`

that returns the longest prefix of `a-seq`

where `pred?`

returns `true`

for every element.

```
(my-take-while odd? [1 2 3 4]) ;=> (1)
(my-take-while odd? [1 3 4 5]) ;=> (1 3)
(my-take-while even? [1 3 4 5]) ;=> ()
(my-take-while odd? []) ;=> ()
```

### Exercise 11

Write the function `(my-drop-while pred? a-seq)`

that drops elements from `a-seq`

until `pred?`

returns `false`

.

```
(my-drop-while odd? [1 2 3 4]) ;=> (2 3 4)
(my-drop-while odd? [1 3 4 5]) ;=> (4 5)
(my-drop-while even? [1 3 4 5]) ;=> (1 3 4 5)
(my-drop-while odd? []) ;=> ()
```

### Recursing over many sequences

The template for linear recursion is very simple and is often *too* simple. For an example, consider the function `(first-in val seq-1 seq-2)`

, which returns `1`

if the value `val`

is found first in `seq-1`

and `2`

if in `seq-2`

. If `val`

is not found in either sequence, `first-in`

returns `0`

. `val`

must not be `nil`

.

```
(defn first-in [val seq-1 seq-2]
(cond
(and (empty? seq-1) (empty? seq-2)) 0
(= (first seq-1) val) 1
(= (first seq-2) val) 2
:else (first-in val (rest seq-1) (rest seq-2))))
```

There’s an obvious reason why `first-in`

doesn’t fit our template for linear recursion: it has three parameters, whereas the template only takes one. We can ignore the first parameter for our purposes, since it does not have bearing on the recursive structure of the computation. `first-in`

is linearly recursive on both its sequence parameters, though.

### Exercise 12

Write the function `(seq= seq-1 seq-2)`

that compares two sequences for equality.

```
(seq= [1 2 4] '(1 2 4)) ;=> true
(seq= [1 2 3] [1 2 3 4]) ;=> false
(seq= [1 3 5] []) ;=> false
```

### Exercise 13

Write the function `(my-map f seq-1 seq-2)`

that returns a sequence of the following kind . The first item is the return value of `f`

called with the first values of `seq-1`

and `seq-2`

. The second item is the return value of `f`

called with the second values of `seq-1`

and `seq-2`

and so forth until `seq-1`

or `seq-2`

ends.

This is actually exactly how `map`

works when given two sequences, but for the sake of practice don’t use `map`

when defining `my-map`

.

```
(my-map + [1 2 3] [4 4 4]) ;=> (5 6 7)
(my-map + [1 2 3 4] [0 0 0]) ;=> (1 2 3)
(my-map + [1 2 3] []) ;=> ()
```

This behaviour of `map`

with multiple sequence arguments can come in handy at times. One useful function to use with it is `vector`

.

`vector`

makes a vector of its arguments.

```
(vector 1 2) ;=> [1 2]
(vector 1 2 3 4) ;=> [1 2 3 4]
```

With `map`

, you can use this to turn two sequences into a sequence of pairs:

```
(map vector [1 2 3] [:a :b :c]) ;=> ([1 :a] [2 :b] [3 :c])
(map vector [1 2 3 4] [2 3 4]) ;=> [1 2] [2 3] [3 4]
```

You can use this to get an indexed version of a sequence:

```
(defn indexed [a-seq]
(let [indexes (range 0 (count a-seq))]
(map vector indexes a-seq)))
(indexed [:a :b :c]) ;=> ([0 :a] [1 :b] [2 :c])
```

Sometimes you need all consecutive pairs from a sequence. This, too, can be achieved with `map`

and `vector`

:

```
(defn consecutives [a-seq]
(map vector a-seq (rest a-seq)))
(consecutives [:a :b :c]) ;=> ([:a :b] [:b :c])
(consecutives [1 2 3 4]) ;=> ([1 2] [2 3] [3 4])
```

### Recursion on numbers

Another common data structure to recurse over are numbers. (Even though you might not think of numbers as data structures!) Recursing over numbers is very similar to recursing over sequences. As an example, let’s define a function to calculate the factorial of a number. (Factorial of \(n\) is \(1 \cdot 2 \cdots (n-1) \cdot n\).)

```
(defn factorial [n]
(if (zero? n)
1
(* n (factorial (dec n)))))
```

The `factorial`

function looks a lot like `sum`

. Given the number `n`

, We have the base case (return 1 if `n`

is zero) and the recursive branch, which multiplies `n`

with the factorial of `(dec n)`

, that is, `(- n 1)`

. To verify that this function really does implement the definition of factorial properly, we can look at how it is evaluated:

```
(factorial 4)
;=> (* 4 (factorial 3))
;=> (* 4 (* 3 (factorial 2)))
;=> (* 4 (* 3 (* 2 (factorial 1))))
;=> (* 4 (* 3 (* 2 (* 1 (factorial 0)))))
;=> (* 4 (* 3 (* 2 (* 1 1)))) ; Base case reached
;=> (* 4 (* 3 (* 2 1)))
;=> (* 4 (* 3 2))
;=> (* 4 6)
;=> 24
```

The line where the base case is reached shows that the function does evaluate to the mathematical expression we wanted.

Let’s look a bit closer at how sequences and numbers are related. Where a sequence is *cons*tructed, numbers are *inc*remented, and where a sequence is destructured with `rest`

, a number is decremented with `dec`

:

```
(inc (inc (inc 0))) ;=> 3
(cons 1 (cons 2 (cons 3 nil))) ;=> (1 2 3)
(dec (dec (dec 3))) ;=> 0
(rest (rest (rest [1 2 3]))) ;=> ()
```

Sequences store more information than numbers – the elements – but otherwise the expressions above are very similar. (The numbers actually encode the length of the sequence. Conversely, sequences can be used to encode numbers. Benjamin Pierce’s Software Foundations is recommended reading if you’re interested in more off-topic esoterica.) With this relationship, we can make the evaluation of `(factorial 4)`

even more similar to our example of `sum`

:

```
(factorial (inc (inc (inc (inc 0))))) ; Unwrap inc with dec
;=> (* 4 (factorial (inc (inc (inc 0))))) ; like cons with rest
;=> (* 4 (* 3 (factorial (inc (inc 0))))) ; almost a haiku
;=> (* 4 (* 3 (* 2 (factorial (inc 0)))))
;=> (* 4 (* 3 (* 2 (* 1 (factorial 0)))))
;=> (* 4 (* 3 (* 2 (* 1 1)))) ; Base case reached
;=> (* 4 (* 3 (* 2 1)))
;=> (* 4 (* 3 2))
;=> (* 4 6)
;=> 24
```

Let’s define the general template for recursion over (natural) numbers, like we did for sequences.

```
(defn eats-numbers [n]
(if (zero? n)
...
(... n ... (eats-numbers (dec n)))))
```

### Exercise 14

Write the function `(power n k)`

that computes the mathematical expression \(n^k\).

```
(power 2 2) ;=> 4
(power 5 3) ;=> 125
(power 7 0) ;=> 1
(power 0 10) ;=> 0
```

### Nonlinear recursion

There are other recursive computations besides linear recursion. Another common type is *tree recursion*. Here *tree* refers again to the shape of the computation. The natural use for tree recursion is with hierarchical data structures, which we will come back to later. Tree recursion can be illustrated with simple processes over numbers. For an example, let’s look at how to compute the following integer series:

Let \(f(n) = \begin{cases} n & \text{ if } n < 3 \\ f(n - 1) + 2 \cdot f(n - 2) + 3 \cdot f(n - 3) & \text{ otherwise} \end{cases}\)

Translating this to Clojure gives us the following program:

```
(defn f [n]
(if (< n 3)
n
(+ (f (- n 1))
(* 2 (f (- n 2)))
(* 3 (f (- n 3))))))
```

(The odd alignment is for clarity.) Consider how this function evaluates:

It is easy to see that the computation forms a tree structure.

### Exercise 15

Compute the \(n\)th Fibonacci number. The \(n\)th Fibonacci number, \(F_n\), is defined as:

- \(F_0 = 0\)
- \(F_1 = 1\)
- \(F_n = F_{n-1} + F_{n-2}\)

Write the function `(fib n)`

which returns \(F_n\).

```
(fib 0) ;=> 0
(fib 1) ;=> 1
(fib 2) ;=> 1
(fib 3) ;=> 2
(fib 4) ;=> 3
(fib 5) ;=> 5
(fib 6) ;=> 8
...
(fib 10) ;=> 55
```

### Sequence operations

We have already implemented some of the sequence functions found from the Clojure’s standard library, namely `map`

and `filter`

. In the following exercises you should use recursion to implement some more.

### Exercise 16

Write the function `(my-repeat how-many-times what-to-repeat)`

that generates a list with `what-to-repeat`

repeated `how-many-times`

number of times.

```
(my-repeat 2 :a) ;=> (:a :a)
(my-repeat 3 "lol") ;=> ("lol" "lol" "lol")
(my-repeat -1 :a) ;=> ()
```

### Exercise 17

Write the function `(my-range up-to)`

that works like this:

```
(my-range 0) ;=> ()
(my-range 1) ;=> (0)
(my-range 2) ;=> (1 0)
(my-range 3) ;=> (2 1 0)
```

### Exercise 18

Write the functions `tails`

and `inits`

that return all the suffixes and prefixes of a sequence, respectively.

```
(tails [1 2 3 4]) ;=> ((1 2 3 4) (2 3 4) (3 4) (4) ())
(inits [1 2 3 4]) ;=> (() (1) (1 2) (1 2 3) (1 2 3 4))
; You can output the tails and inits in any order you like.
(inits [1 2 3 4]) ;=> ((1 2) () (1 2 3) (1) (1 2 3 4))
```

*Hint:* You can use `reverse`

and `map`

.

```
(reverse [1 2 3]) ;=> (3 2 1)
(reverse [2 3 1]) ;=> (1 3 2)
```

### Exercise 19

Write the function `(rotations a-seq)`

that, when given a sequence, returns all the rotations of that sequence.

```
(rotations []) ;=> (())
(rotations [1 2 3]) ;=> ((1 2 3) (2 3 1) (3 1 2))
(rotations [:a :b]) ;=> ((:a :b) (:b :a))
; The order of rotations does not matter.
(rotations [:a :b]) ;=> ((:b :a) (:a :b))
(rotations [1 5 9 2]) ;=> ((1 5 9 2) (2 1 5 9) (9 2 1 5) (5 9 2 1))
(count (rotations [6 5 8 9 2])) ;=> 5
```

Keep in mind the function `concat`

.

```
(concat [1 2 3] [:a :b :c]) ;=> (1 2 3 :a :b :c)
(concat [1 2] [3 4 5 6]) ;=> (1 2 3 4 5 6)
```

### Passing state

Sometimes when recursing over a structure we want to keep track of something. For an example, we might want to count how many elements we have processed, or how many `:D`

keywords we have seen. How do we do this, in the absence of state in our language? (Or at least in the absence of instructions on how to use state on these pages!)

The answer is two-fold: we store the state explicitly in a parameter we pass back to ourselves on each recursion, and we hide the state from the users of our function by using a helper function that we give an initial empty state to as a parameter.

Here’s an example of a function that counts how many times a sequence contains a given element:

```
(defn count-elem-helper [n elem coll]
(if (empty? coll)
n
(let [new-count (if (= elem (first coll))
(inc n)
n)]
(count-elem-helper new-count
elem
(rest coll)))))
(defn count-elem [elem coll]
(count-elem-helper 0 elem coll))
```

First, we define a helper function, `count-elem-helper`

. It takes three parameters:

`n`

, which keeps count of how many times we have seen`elem`

`elem`

, which is the element we are looking forand

`coll`

, which is the collection the function recurses over.

With this helper function, our definition of `count-elem`

is a simple call to `count-elem-helper`

with `n`

initialized to 0. This way users of `count-elem`

do not need to provide the initialization argument for `n`

.

### Exercise 20

Write the function `(my-frequencies a-seq)`

that computes a map of how many times each element occurs in a sequence. E.g.:

```
(my-frequencies []) ;=> {}
(my-frequencies [:a "moi" :a "moi" "moi" :a 1]) ;=> {:a 3, "moi" 3, 1 1}
```

You’ll want to structure your code like this:

```
(defn my-frequencies-helper [freqs a-seq]
...)
(defn my-frequencies [a-seq]
(frequencies-helper {} a-seq))
```

Where `my-frequencies-helper`

is a recursive helper function.
### Exercise 21

Write the function `(un-frequencies a-map)`

which takes a map produced by `my-frequencies`

and generates a sequence with the corresponding numbers of different elements.

```
(un-frequencies {:a 3 :b 2 "^_^" 1}) ;=> (:a :a :a "^_^" :b :b)
(un-frequencies (my-frequencies [:a :b :c :a])) ;=> (:a :a :b :c)
(my-frequencies (un-frequencies {:a 100 :b 10})) ;=> {:a 100 :b 10}
```

The order of elements in the output sequence doesn’t matter.

Hint 1: Remember that you can use `first`

and `rest`

on a map too!

```
(first {:a 1 :b 2}) ;=> [:a 1]
(rest {:a 1 :b 2 :c 3}) ;=> ([:b 2] [:c 3])
```

Hint 2: There are multiple ways to implement this, but consider using `concat`

and `repeat`

.
### Merging and sorting

As a grande finale, let’s implement the classic merge sort. We have split the task into smaller exercises.

### Exercise 22

Implement `(my-take n coll)`

that returns `n`

first items of coll.

```
(my-take 2 [1 2 3 4]) ;=> (1 2)
(my-take 4 [:a :b]) ;=> (:a :b)
```

### Exercise 23

Implement `(my-drop n coll)`

that returns all but the `n`

first items of coll.

```
(my-drop 2 [1 2 3 4]) ;=> (3 4)
(my-drop 4 [:a :b]) ;=> ()
```

### Exercise 24

Implement the function `(halve a-seq)`

that takes a sequence and returns one vector with two elements. The first element is the first half of `a-seq`

and the second element is the second half of `a-seq`

.

To turn a result of division into an integer use `int`

.

`(int (/ 7 2)) ;=> 3`

```
(halve [1 2 3 4]) ;=> [(1 2) (3 4)]
(halve [1 2 3 4 5]) ;=> [(1 2) (3 4 5)]
(halve [1]) ;=> [() (1)]
```

### Exercise 25

Write the function `(seq-merge a-seq b-seq)`

that takes two (low to high) sorted number sequences and combines them into one sorted sequence. Don’t use sort (nor implement it yourself, yet).

```
(seq-merge [4] [1 2 6 7]) ;=> (1 2 4 6 7)
(seq-merge [1 5 7 9] [2 2 8 10]) ;=> (1 2 2 5 7 8 9 10)
```

### Exercise 26

Write the function `(merge-sort a-seq)`

that implements merge sort.

The idea of merge sort is to divide the input into subsequences using `halve`

, sort the subsequences recursively and use the `seq-merge`

function to merge the sorted subsequences back together.

Conceptually:

- If the sequence is 0 or 1 elements long, it is already sorted.
- Otherwise, divide the sequence into two subsequences.
- Sort each subsequence recursively.
- Merge the two subsequences back into one sorted sequence.

```
(merge-sort [4 2 3 1])
;=> (seq-merge (merge-sort (4 2))
; (merge-sort (3 1)))
;=> (seq-merge (seq-merge (merge-sort (4))
; (merge-sort (2)))
; (seq-merge (merge-sort (3))
; (merge-sort (1))))
;=> (seq-merge (seq-merge (4) (2))
; (seq-merge (3) (1)))
;=> (seq-merge (2 4) (1 3))
;=> (1 2 3 4)
```

```
(merge-sort []) ;=> ()
(merge-sort [1 2 3]) ;=> (1 2 3)
(merge-sort [5 3 4 17 2 100 1]) ;=> (1 2 3 4 5 17 100)
```

## Encore

The following exercises are ment to be tricky. So don’t dwell too long on them. Move along and come back later.

These exercises will give extra points.

### Exercise 27

2 points

Write the function `split-into-monotonics`

that takes a sequence and returns the sequence split into monotonic pieces. Examples:

```
(split-into-monotonics [0 1 2 1 0]) ;=> ((0 1 2) (1 0))
(split-into-monotonics [0 5 4 7 1 3]) ;=> ((0 5) (4 7) (1 3))
```

*Hint:* You might find useful the functions `take-while`

, `drop`

and `inits`

. Make sure that your `inits`

returns the prefixes from the shortest to the longest.

`(inits [1 2 3 4]) ;=> (() (1) (1 2) (1 2 3) (1 2 3 4))`

### Exercise 28

3 points

Given a sequence, return all permutations of that sequence.

```
(permutations #{})
;=> (())
(permutations #{1 5 3})
;=> ((1 5 3) (5 1 3) (5 3 1) (1 3 5) (3 1 5) (3 5 1))
```

The order of the permutations doesn’t matter.
### Exercise 29

3 points

Given a set, return the powerset of that set.

```
(powerset #{}) ;=> #{#{}}
(powerset #{1 2 4}) ;=> #{#{} #{4} #{2} #{2 4} #{1} #{1 4} #{1 2} #{1 2 4}}
```