ABSTRACT DATA STRUCTURES | RECURSION

Topics from the IB Computer Science Specification 2014

ON THIS PAGE
SECTION 1 | WHAT IS RECURSION
SECTION 2 | RECURSION VS LOOPS
SECTION 3 | FACTORIALS WITH RECURSION
SECTION 4 | FIBONACCI WITH RECURSION
SECTION 5 | TRACING A RECURSIVE CALL IN JAVA
​SECTION 6 | TRACING A RECURSIVE CALL IN PYTHON

ALSO IN THIS TOPIC
YOU ARE HERE | RECURSION
DATA STRUCTURES
LINKED LISTS
TREES
APPLICATION
TOPIC 5 REVISION
KEY TERMINOLOGY
TOPIC 5 ANSWERS

---

SECTION 1 | WHAT IS RECURSION

" In programming, recursion is where a function calls itself"
Recursion is a method used to solve a big problem by repeating smaller problems in a pattern that eventually reach the end result. In programming terms we can create a function that calls itself until a condition is met. When using a recursive method we need to consider the two principles;
1: The pattern (recursion) to follow. (Recursive Case)
2: When the goal has been reached where to stop. (Base Case)

​SECTION 2 | WHAT IS THE DIFFERENCE BETWEEN LOOPS AND RECURSION?

Everything recursion can do, loops can do. So why use recursion?
For loops in Python or Java and Do loops in some early languages such as Fortran can nest loops(put loops within a loop), by nesting loops we can achieve the same as using a recursive method. Using nested loops can get complicated, heavy on the compiler and process heavy. Previous limitations on how deep loops can be nested, with early programming languages like Fortran allowing for around 8 nested loops, although currently 256+ nested loops in some programming languages are accepted they can get messy and recursion can provide a more efficient solution to solving the same problem. 

Recursion can still cause processing problems with the amount of data that is stacked up waiting to be processed, and this is known as a stack overflow, this is discussed in more detail in the Stacks and Queues section.

Whilst recursion is a much more elegant solution to nested loops, in the past there may not be many real world examples of where recursion is needed because loops cannot deal with the situation, however we may see more recursive methods used in future programming as computational solutions may be more frequently done 'on the fly' and compiling speed becomes more crucial. A counter argument for future use of recursion is that we may see more programs been written in low level languages, as more and more future programs will be written by computers therefore reducing the load in the compiling stage. Furthermore is the impact quantum computers may have with the change in programming languages for quantum computing. 

Some practical uses for recursion include:

• Tree Traversal: When dealing with a tree data structure, such as a binary search tree, using recursion can be an effective way to traverse the tree in a depth-first search manner.
• Sorting: Recursion can be used to implement several sorting algorithms, such as quicksort and mergesort.
• Fractals: Fractals are shapes that have self-similar patterns, and they can be generated using recursive algorithms.

SECTION 3 | FACTORIALS WITH RECURSION

Factorials are simply products of all the numbers below the given numbers. Often notated with an explanation mark, for example factorial 4 would be 4!. To calculate 4! you simply do 1x2x3x4 = 24, so factorial 4 is 24. (! means to multiple by decreasing positive integers). Below is example code of a recursive method to calculate the factorial of a given number.

Code Editor

​SECTION 4 | FIBONACCI WITH RECURSION

The Fibonacci sequence is calculated by adding the two previous numbers together to generate the next number in the sequence. The Fibonacci sequence in the code below has two recursive calls, each containing one of the two previous numbers needed to calculate the next number.

SECTION 5 | TRACE A RECURSIVE CALL IN JAVA

To better understand what is happening when a single recursive call and multiply recursive call is been made watch this video by Carl Turland made for IB Computer Science students and coded in Java.

SECTION 6 | TRACE A RECURSIVE CALL IN PYTHON

To better understand what is happening when a single recursive call and multiply recursive call is been made watch this video by Jason Machin made for IB Computer Science students and coded in Python.

ALSO IN THIS TOPIC

RECURSION
DATA STRUCTURES
LINKED LISTS
TREES
APPLICATION
TOPIC 5 REVISION
KEY TERMINOLOGY
TOPIC 5 ANSWERS