A Level CS (9618) 19 Computational Thinking and problem solving

19.1 Algorithms, 19.2 Recursion

Binary search

"a method of searching an ordered list by testing the value of the middle item in the list and rejecting the half of the list that does not contain the required value."

Insertion sort

"a method of sorting data in an array into alphabetical or numerical order by placing each item in turn in the correct position in the sorted list."

Binary tree

"a hierarchical data structure in which each parent node can have a maximum of two child nodes."

Graph

"a non-linear data structure consisting of nodes and edges."

Dictionary

"an abstract data type that consists of pairs

Big O notation

"a mathematical notation used to describe the performance or complexity of an algorithm."

Recursion

"a process using a function or procedure that is defined in terms of itself and calls itself."

Base case

"a terminating solution to a process that is not recursive."

General case

"a solution to a process that is recursively defined."

Winding

"process which occurs when a recursive function or procedure is called until the base case is found."

Unwinding

"process which occurs when a recursive function finds the base case and the function returns the values."