Recursive algorithms Flashcards
What does 0! zero factorial equal
It equals 1
What do recursive algorithms use?
They use stack data structures
What must a recursive routine have?
- It must have a stopping condition or base case (which means it will stop calling itself and start to unwind)
- For input values (excluding the stopping condition) it must call itself
- The stop condition must be reached after a finite number of calls
Why must there be a finite point before the stopping point?
if there isn’t the stack will overflow (as there is no more space in the stack)
What is a recursive subroutine?
A subroutine that is defined in terms of itself
What three things are held in a stack frame?
- The return address,
- The parameters
- The local variables
used in the subroutine are held in the stack frame in the call stack
What sort of algorithm is used for tree traversals?
Recursive algorithms
What is the algorithm for an in order tree traversal?
- Traverse the left subtree
- Visit the root node
- Traverse the right subtree
What is the algorithm for an post order tree traversal?
- Traverse the left subtree
- Traverse the right subtree
- Visit the root node
What is the algorithm for an pre order tree traversal?
- Visit the root node
- Traverse the left subtree
- Traverse the right subtree
How can a binary tree be represented in memory?
A binary tree can be represented in memory by three 1 dimensional arrays
What position in an array/list is the value of the root node stored in?
It is stored as the first element of the list
What three columns are required for storing a binary tree as three arrays/lists in memory?
1 column to identify the data in each node, 1 column holding the left pointers to the left subtrees and 1 column holding the right pointers to the right subtrees.
What can in order traversal algorithms be used for?
Can be used to output the values held in the nodes in alphabetic or numerical sequence.
What can post order traversal algorithms be used for?
Can be used for writing algebraic expressions in Reverse Polish Notation
What can pre order traversal algorithms be used for?
Can be used for
- copying a tree
- producing a prefix expression from an expression tree
What is a divide-and-conquer algorithm?
An algorithm that uses recursion to break down a problem into two or more sub-problems so the problem is simpler to solve
