# Building abstractions with recursive functions and higher-order functions¶

In programming, we control the intellectual complexity of our programs
by **building abstractions** that hide details when appropriate.
You already know of one such means to build abstractions in Python:
the ability to **define your own functions**.
This allows you to chunk compound operations as conceptual units, give them a name and manipulate them.
In this module, you will explore two other means to build abstractions with functions: **recursive functions** and **higher-order functions**.

## Recursive functions¶

**1. Watch the introduction video and read the following summary paragraph.**

**Summary.**
Recursive definitions allow us to describe many complex concepts in a simple and elegant way.
Likewise, *recursive functions* in Python allow us to define methods for solving problems in a simple and elegant way.
When doing so, we think in terms of *base cases*, for which there is an immediate solution,
and *recursive cases*, for which we can define the solution to our problem in terms of solutions to smaller versions of the same problem.
Once the solution has been defined in such a way, translating it into Python code is a snap.
This frees us from without having to worry about a whole series of questions that would arise if we were to solve the problem iteratively
(how to traverse sub-problems, how to keep track of intermediate results, what the iteration variable is, what the stop conditions are…).
In other words, we have abstracted the solution from the nitty-gritty details of control flow, memory, etc.

**2. Read section 16.1 to 16.6 of the interactive book thinkcspy at:** https://runestone.academy/runestone/books/published/thinkcspy/IntroRecursion/toctree.html

Sections 16.5. and 16.6 use the `turtle`

graphics module which you may not be familiar with, but you should still be able to grasp the code easily.
You can skip them if you want, but visualization is a powerful way to learn about recursion.

**3. Do some of the following practice exercises.**

You can move to the next section whenever you feel ready to learn more, but make sure to do at least two exercises (like any other programming concepts/techniques, recursive functions cannot be understood without practice).

**Time to complete.** [*]: short, [**]: medium, [***]: long.

**Exercise 1.** [*] Write a recursive function to reverse a list. (Hint: to concatenate two lists, use the ‘+’ operator).

**Exercise 2.** [*] Write a recursive function to reverse a list.

**Exercise 3.** [**] Write a script that displays the Koch snowflake (see on wikipedia) using a recursive function.
You can use the `turtle`

graphics module to draw on screen
(as shown in section 16.5 of thinkcspy).

A solution: link to code.

**Exercise 4.** [**] Write a script that returns the pathnames of all the files ending in `.txt`

contained inside a directory (at any depth of the hierarchy). You will need to use `os.listdir()`

and `os.path.isdir()`

.

**Exercise 5.** [**] Write a recursive function to generate all permutations of a list of values. (This could be useful, e.g., to do a permutation test for statistical analyses.)

**Exercise 6.** [***] Write a recursive function to evaluate an arithmetic expression given in Polish notation (i.e. prefix notation, see on wikipedia)

**Exercise 7.** [***] Produce strings from the MIU formal grammar and investigate the MU puzzle. See detailed explanations on the MU Puzzle.

Side remark: in some cases, recursive functions can take a prohibitive amount of time and/or memory. This happens when the same computations are performed many times. This issue can be addressed using *memoization*. If you are curious, you can read the article Memoization in Python

## Higher-order functions¶

**1. Watch the introduction video.**

**2. Read section 1.6 Higher-Order Functions of the online textbook at:**
https://wizardforcel.gitbooks.io/sicp-in-python/content/6.html

This textbook is an adaptation for Python of the textbook cited at the bottom of the page. (Author’s note: I haven’t checked out the rest of this adaptation. I recommend to read the original book if you want to learn more.)

**Stop and think:** In the section of the book you have read, the functions `summation`

and `iter_improve`

were implemented iteratively, using a `while`

statement. Can you think of how to implement them recursively?

**3. Do some of the following practice exercises.**

**Time to complete.** [*]: short, [**]: medium, [***]: long.

**Exercise 1.** [*]
Write a `product`

function to compute the product of the values of a function at points over a given range (the function should be an argument of `product`

).
Then, define a function to compute the factorial in terms of `product`

.
Finally, use `product`

to compute an approximation to pi using the Wallis product formula (see on wikipedia).

**Exercise 2.** [**]
The `summation`

function (from the textbook section you read)
and the `product`

function (defined above)
can be defined as special cases of an even more general `reduce`

function
which has two more arguments:
`binary_operator`

(which specifies what operation should be applied to reduce all the values to a single one)
and `neutral_element`

(which specifies what base value should be used when the range is empty).
Write such a `reduce`

function, and then define `summation`

and `product`

functions in terms of `reduce`

.
Make sure to test your functions.

**Exercise 3.** [**]
Write a function that finds a fixed point of a function
(see on wikipedia)
starting from an initial guess value, which could be defined as:
`find_fixed_point(f, initial_value, error_margin)`

.
The returned value, `x`

, should be such that `abs(f(x) - x) < error_margin`

. Then, define a function to calculate the square root of a positive number, using the property that the square root of x is a fixed point
for the function y -> 1/2 (y + x/y).
Make sure to test your square root function.

**Exercise 4.** [**]
Write a function to numerically compute any statistic of an arbitrary random variable.
The statistic and the random variable should both be functions which are given as argument.

(Hints. A statistic can be defined as a function of a collection of samples, e.g. sample mean, sample variance. A random variable can be defined as a function that, when it is called, generates one sample.)

## Reference¶

This module was inspired by:
Abelson, Harold, and Gerald Jay Sussman. *Structure and interpretation of computer programs*. The MIT Press, 1996.

It is an excellent computer science textbook. If you are curious, go check it out, it is freely available online as pdf and as a web document.