19.2 Recursion

##### What is meant by recursion

- A process using a function or procedure defined in terms of itself / calls itself.
- A recursive process must have a base case (which is a way to return without making a recursive call) // terminating solution // concept of unwinding described
- There must (also) be a general case where the recursive call takes place.
##### Essential features of recursion
- Must have a base case/stopping condition
- Must have a general case
- … which calls itself (recursively) // Defined in terms of itself
- … which changes its state and moves towards the base case
- Unwinding can occur once the base case is reached.
##### Why a stack is a suitable Abstract Data Type (ADT) to implement recursion.
- A stack is a LIFO data structure
- Each recursive call is pushed onto the stack and is then popped as the function ends
- Enables backtracking/unwinding to maintain the required order.
##### ADTs

- Linked List
- Queue
- Binary Tree

Stack – a list containing several items operating on the last in, first out (LIFO) principle. Items can be added to the stack (push) and removed from the stack (pop). The first item added to a stack is the last item to be removed from the stack.

Queue – a list containing several items operating on the first in, first out (FIFO) principle. Items can be added to the queue (enqueue) and removed from the queue (dequeue). The first item added to a queue is the first item to be removed from the queue.

Linked list – a list containing several items in which each item in the list points to the next item in the list. In a linked list a new item is always added to the start of the list.