Recursive algorithms

Question 1

What does 0! zero factorial equal

Answer 1

It equals 1

Question 2

What do recursive algorithms use?

Answer 2

They use stack data structures

Question 3

What must a recursive routine have?

Answer 3

• 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

Question 4

Why must there be a finite point before the stopping point?

Answer 4

if there isn’t the stack will overflow (as there is no more space in the stack)

Question 5

What is a recursive subroutine?

Answer 5

A subroutine that is defined in terms of itself

Question 6

What three things are held in a stack frame?

Answer 6

• The return address,
• The parameters
• The local variables
  used in the subroutine are held in the stack frame in the call stack

Question 7

What sort of algorithm is used for tree traversals?

Answer 7

Recursive algorithms

Question 8

What is the algorithm for an in order tree traversal?

Answer 8

• Traverse the left subtree
• Visit the root node
• Traverse the right subtree

Question 9

What is the algorithm for an post order tree traversal?

Answer 9

• Traverse the left subtree
• Traverse the right subtree
• Visit the root node

Question 10

What is the algorithm for an pre order tree traversal?

Answer 10

• Visit the root node
• Traverse the left subtree
• Traverse the right subtree

Question 11

How can a binary tree be represented in memory?

Answer 11

A binary tree can be represented in memory by three 1 dimensional arrays

Question 12

What position in an array/list is the value of the root node stored in?

Answer 12

It is stored as the first element of the list

Question 13

What three columns are required for storing a binary tree as three arrays/lists in memory?

Answer 13

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.

Question 14

What can in order traversal algorithms be used for?

Answer 14

Can be used to output the values held in the nodes in alphabetic or numerical sequence.

Question 15

What can post order traversal algorithms be used for?

Answer 15

Can be used for writing algebraic expressions in Reverse Polish Notation

Question 16

What can pre order traversal algorithms be used for?

Answer 16

Can be used for

• copying a tree
• producing a prefix expression from an expression tree

Question 17

What is a divide-and-conquer algorithm?

Answer 17

An algorithm that uses recursion to break down a problem into two or more sub-problems so the problem is simpler to solve