**The fourth lecture covered slides 10-60 in the lecture slides.**

You should have learnt about recursion, the definition of recursive functions, and recursive data structures (now you know that a list is a recursive data structure).

Remember to carry on reading chapters 4 to 7 in the textbook (pp. 67-176).

**Extra note:**

In the last two lectures you’ve been introduced to *QuickCheck*. QuickCheck does *random testing* on functions. This is a very useful tool for testing functions, but it relies on the fact that give some input a function always has the same output. This is of course true in Haskell. If f(x)=y then f(x) always equals y.

You give QuickCheck your function and a property that is true of all results of the function. QuickCheck generates a set of random inputs to your function and then checks that for every input the property is true. Of course, you have to be careful about the property you choose!

In other languages random testing is not quite as useful. A Java method, for example, does not always return the same result for some input. In Java f(x) does not always equal y. For example, f might depend on something in memory or some user input. In Haskell this is not the case.

One of the most powerful aspects of functional programming is this *absence of state*, that is the state of the world (memory, hard disk, user, network, etc.) does not affect the outcome of the function. Later on in the course you will learn how to deal with these necessary interactions with the world.

— *Chris*

If you’re having trouble working out how to define recursive functions, the discussion on p162-165 of the book is very good. As it says, the crucial question to ask is:

which is explored through a short series of very typical examples.