19.2 Recursion

##### What is meant by recursion

- A technique used to solve problems using a function/procedure/subroutine that calls itself (general case) until the terminating condition / base case is achieved, when no further recursive calls are made
- A recursive process must have a base case
- 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.