Fundamentals of algorithms

shortest path for an unweighted graph

Navigating a maze

copies a tree

outputs the contents of a binary search tree in ascending order

emptying a tree

Easier for computer to analyse Do need brackets so don’t have to keep track of parentheses

Used in interpreters based on a stack for example Postscript and bytecode.

continually divides a list by two, eliminating the part of the list that cannot have your item in it O(log n)

checks each element to see if it matches the target O(n)

swaps the largest with the smallest until list is in order O(n^2) {example of a particularly inefficient sorting algorithm, time-wise.}

splits the input into two lists of similar sizes, sorts them recursively and merges them back together into one sorted lists O(nlog n)

navigation system to find most efficient routes between locations

iterative solutions often start small and build up recursion solutions often start big and break the problem down

iterative solutions often start small and build up recursion solutions often start big and break the problem down pros: recursive solutions can be more concise and readable iterative solutions often execute faster cons: recursion can run infinitely when the the general case doesn’t move towards the stopping case / can take up more memory iteration can run infinitely if an indefinite loop is used and the condition never changes

Subroutine that calls itself

keeps track of subroutines that have started but havent finished