# 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