IB Computer Science HL Paper 1 Topic 5

Recursion

Recursion

• A method that calls itself

• Involves the use of stacks to store data that will be returned at end

• Can be memory intensive if many recursive calls are made

Characteristics of a stack

• A data structure

• LIFO

• dynamic

Stack access methods

• push()

• pop()

• isEmpty()

Characteristics of a queue

• FIFO

• dynamic

Queue access methods

• enqueue()

• dequeue()

• isEmpty()

Real world examples of queues

• Printer queues

• Computer modelling of real-life queues (like in supermarkets)

Linked lists

• Linear collection of nodes, which are self-referential

• Nodes connected by pointer links

Features of a doubly linked list

• Single head, single tail

• Each node has two pointers - one to next, one to previous

Features of a circular linked list

• Single head

• One pointer for each element

• Last element’s pointer points to head

Binary trees

Parent

• A node in a tree that has children (left, right or both)

Root

• The top node in a tree

Subtree

• A parent with children within another parent-child relationship

Dynamic data structures pros and cons

Pros

• Can change size while program is running

• Makes efficient use of memory

• Storage no longer required can be returned to the system for other use

Cons

• Difficult to program

• Can be slow / complex to implement

• A linked list only allows serial (in order) search

Static data structures pros and cons

Pros

• Easy to program

• Easy to check for overflow

• An array allows random access

• Does not change in size while program is running

Cons

• Can waste space

• Programmer has to estimate space needed, could be wrong