Recursive algorithms Flashcards Preview

Paper 1 - Computer Science > Recursive algorithms > Flashcards

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

What does 0! zero factorial equal

It equals 1

2

What do recursive algorithms use?

They use stack data structures

3

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

4

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)

5

What is a recursive subroutine?

A subroutine that is defined in terms of itself

6

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

7

What sort of algorithm is used for tree traversals?

Recursive algorithms

8

What is the algorithm for an in order tree traversal?

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

9

What is the algorithm for an post order tree traversal?

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

10

What is the algorithm for an pre order tree traversal?

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

11

How can a binary tree be represented in memory?

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

12

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

13

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.

14

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.

15

What can post order traversal algorithms be used for?

Can be used for writing algebraic expressions in Reverse Polish Notation

16

What can pre order traversal algorithms be used for?

Can be used for
- copying a tree
- producing a prefix expression from an expression tree

17

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