Recursive algorithms Flashcards Preview

Paper 1 - Computer Science > Recursive algorithms > Flashcards

Flashcards in Recursive algorithms Deck (17)
Loading flashcards...
1
Q

What does 0! zero factorial equal

A

It equals 1

2
Q

What do recursive algorithms use?

A

They use stack data structures

3
Q

What must a recursive routine have?

A
  • 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
4
Q

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

A

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

5
Q

What is a recursive subroutine?

A

A subroutine that is defined in terms of itself

6
Q

What three things are held in a stack frame?

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

What sort of algorithm is used for tree traversals?

A

Recursive algorithms

8
Q

What is the algorithm for an in order tree traversal?

A
  • Traverse the left subtree
  • Visit the root node
  • Traverse the right subtree
9
Q

What is the algorithm for an post order tree traversal?

A
  • Traverse the left subtree
  • Traverse the right subtree
  • Visit the root node
10
Q

What is the algorithm for an pre order tree traversal?

A
  • Visit the root node
  • Traverse the left subtree
  • Traverse the right subtree
11
Q

How can a binary tree be represented in memory?

A

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

12
Q

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

A

It is stored as the first element of the list

13
Q

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

A

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.

14
Q

What can in order traversal algorithms be used for?

A

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

15
Q

What can post order traversal algorithms be used for?

A

Can be used for writing algebraic expressions in Reverse Polish Notation

16
Q

What can pre order traversal algorithms be used for?

A

Can be used for

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

What is a divide-and-conquer algorithm?

A

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