DATA STRUCTURES
4.6 RECURSION

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)

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. 

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.

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.

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.

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.

ACTIVITY 1

APPROXIMATE TIME: 2 HOURS

MATERIALS NEEDED:
1: Paper
2: Computer and coding platform
3: Optional: If you are doing GCSE, IB or A-Level then use the course pseudocode guide to ensure you use pseudocode syntax as expected.

TASK 1: Create a program to do the following:
1: Write a none recursive version of a factorial program in pseudocode - check you code with your teacher.
2: Write the same program in your preferred programming language.
3: Write a recursive factorial program or copy the version from above.
4: Add a timer to both versions of your program
5: Run both programs with various recursive inputs (5, 10, 100, 1000, 10000) and record the time to compute each.

TASK 2: Trace tables
1: After watching the video above by Carl Turland on tracing recursive algorithms - try to complete the next two tasks without needing to refer back to the video.
2: Create and complete a trace table for the non recursive version of your program.
3: Create and complete a trace table for your recursive program.

NEED MORE HELP