Lecture 6 - Recursion

What are the 5 steps of making a recursive function?

1. Define the type

2. Enumerate the cases

3. Define base cases

4. Define reduction of other cases to simpler ones

5. Generalise and simplify.

What is the call stack?

Each recursive call goes onto the call stack. Too many calls results in a stack overflow in most languages, but Haskell is able to support deeper stacks.

What are the 4 types of recursion and what do they mean?

• Linear - one recursive call

• Multiple - multiple recursive calls

• Direct - calls itself

• Indirect/mutual - functions recursively call each other.

What is tail recursion?

When the last call of the function calls itself with new arguments, or returns a value. Tail recursion use constant stack space and an accumulator.

If you want to convert between an imperative loop and a functional recursive function, what do you do?

Make the loop variables into arguments and write a tail recursive function.