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.

SECTION 6 | EXAMPLE USES

Recursive algorithms are particularly well-suited for problems that can be broken down into smaller instances of the same problem, a characteristic often referred to as self-similarity. These algorithms solve the problem by calling themselves with a subset of the original problem until they reach a base case, which is a condition without further recursion. Recursive approaches are a staple in computer science, offering elegant solutions for a variety of complex problems. Here are some types of problems where recursive algorithms shine:

1. Divide and Conquer Problems
These problems can be divided into smaller instances of the same problem. Recursion simplifies the solution by tackling each smaller instance with the same logic. Examples include:

• Sorting algorithms | QuickSort and MergeSort divide the array into smaller arrays that are sorted independently.
• Searching algorithms |  Binary Search divides the search space in half with each step, significantly reducing the number of comparisons.

2. Dynamic Programming Problems
Many dynamic programming problems, where the solution involves solving subproblems and combining their results, can be approached recursively. Examples include:

• Fibonacci number calculation | Each number is the sum of the two preceding ones.
• Knapsack problem |Maximising the total value of items that can fit into a bag with a given capacity.

3. Tree and Graph Traversals
Trees and graphs are inherently recursive structures (a tree node may point to other nodes as its children, and a graph may have cycles). Recursion naturally aligns with operations like:

• Tree traversal algorithms | Pre-order, in-order, and post-order traversals.
• Graph algorithms | Depth-first search (DFS) and certain implementations of breadth-first search (BFS).

4. Combinatorial Problems
Problems that involve exploring all possible combinations or permutations, such as generating power sets or solving puzzles (e.g., the Towers of Hanoi), are well-suited for recursive solutions because:

• They involve choosing an element and exploring all scenarios with and without that element.
• Recursive algorithms can elegantly backtrack to explore different branches of the solution space.

5. Mathematical Problems
Many mathematical problems, especially those involving iterative processes or defined by recurrence relations, are naturally suited for recursion. Examples include:

• Calculating factorials | n! is defined as n x (n-1)! for n > 0 with a base case of 0! = 1
• GCD (Greatest Common Divisor) | The Euclidean algorithm to find the GCD of two numbers is inherently recursive.

Advantages and Considerations
While recursive algorithms often provide a more straightforward and readable solution, they come with their own set of considerations:

• Stack Overflow | Deep recursion can lead to stack overflow errors if the recursion depth exceeds the stack size.
• Performance | Recursive calls involve additional overhead compared to iterative solutions. In some cases, memoization or converting to an iterative form using a stack can mitigate performance issues.

Recursive algorithms excel in solving problems that exhibit inherent self-similarity, can be decomposed into simpler or smaller instances of the same problem, or have a natural hierarchical structure.

ALSO IN THIS TOPIC

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