CC Logo

Position Paper: Recursion

Short Form Essay

This essay was written for a year three module, and uses the idea of Recursion to help explain why programming paradigms are useful.


---


Contents:
-What are Programming Paradigms and Recursion?
-How does Recursion work?
-Recursion versus Iteration
-Where is Recursion Used?
-Real World Applications: Quicksort
-Conclusion
References & Bibliography


What are Programming Paradigms and Recursion?

A Programming Paradigm is a logical approach that is used to describe how a programming language functions. There are many types of paradigm, and a language may utilize multiple paradigms, but several main ones are – object-oriented (which is concerned with modularity, and uses hierarchical classes and objects of those classes); functional (where mathematical functions are computed in the form of expressions); imperative (where the program is defined step by step with statements) and logic (where a program is defined with logical rules and relations between them).

Recursion is the application of recursive techniques, usually within computer programming in order to solve a problem. Within programming, a recursive function is one that as one of the steps made during execution; it will call itself, causing another iteration of the function to execute. This means that it will repeatedly loop until a result is achieved, at which point the loop should stop and return the result.

Recursion is a tool that can be used in languages that take from many programming paradigms, but it is especially important in functional programming, where variables that can be changed (mutable variables) are avoided, so loops are better performed through recursion than iteration.


How does Recursion work?

One of the most common uses of Recursion within programming is to break a larger problem down into smaller elements, and then repeatedly solve these smaller problems in order to build up to the solution of the original problem. One commonly used example of this application of recursion is a Factorial function.

According to Hui, R and Iverson, K (1995), a simple example of a recursive function is one that takes a positive integer as an input and returns the multiplication of that number by all the positive integers that are less than it. For instance, if the input was 3, the actual equation would be “3 * 2 * 1”. This is called a Factorial function, and is commonly identified by “n!”, where n is the input value. For the example of “3*2*1”, it would be identified as “3!”.

One important issue to consider with recursion is that by calling itself over and over again, it will eventually reach a point where the operations being performed are unnecessary, wrong or act in such a way that will cause errors. In order to avoid this, the recursive function must include a base case (also known as a halting case) that stops the recursion when certain conditions are fulfilled. For example, with a Factorial recursion function, the function will have to stop the recursion when the value is zero (which is assumed to be 1), as negative values are beyond the scope of Factorial functions.

As noted by McCaffrey, J (2006), there is another issue that arises when using recursion to calculate Factorial values – eventually, the end value will be large enough that it will be impossible to store in a conventional data type. He notes that if there are only a small amounts of results that can be calculated and stored, there is little reason to calculate each time and instead proposes that the values could be calculated once and then stored in a table and checked when needed.

Recursion versus Iteration

In addition to using either a recursive function or a table of values to implement a Factorial function, there is another main method – Iteration. Whereas recursion works by breaking the problem down until the final stage and then working through each stage, an iterative solution starts from the first value (usually one) and then repeats the task until it reaches the solution.

For example, consider the computation of the factorial of three (the answer of which is 6) through both of these pseudocode methods:

:

Factorial_R(3)

Factorial_I(3)

3 is not 1

f = 1

3 * Factorial_R(2)

Start Loop

2 is not 1

i = 1: 1 is less than or equal to 3

2 * Factorial_R(1)

f = 1 * 1 = 1

1 is 1

i = 2: 2 is less than or equal to 3

Return 1

f = 1 * 2 = 2

Return 2*1 = 2

i = 3: 3 is less than or equal to 3

Return 3*2 = 6

f = 2 * 3 = 6


i = 4: 4 is not less than or equal to 3


Return f = 6

As can be seen, the factorial method results in more method calls (which can cause problems) and in this instance, results in easier to read code, whereas iteration takes slightly more steps (for this value of n – each run of the loop is three steps for the recursive method and two for the iterative method, meaning that recursion will start taking more steps when n equals 6 or more). Each of these provides the correct solution.

Another commonly given example of a recursive function is one used to calculate a series of numbers called the Fibonacci sequence – a sequence where for every positive integer higher than two (one and two are just equal to one within the sequence), the result is the Fibonacci values of the previous two numbers in order (thus, as stated by Lippert (2004), fib (n) = fib(n-1) + fib(n-2)). However, Lippert (2004) also notes that this is a poor example as it can be computed much more efficiently through iteration.

There are several reasons why iteration may be better suited to a task than recursion, depending on the circumstances – for instance, in some languages the extra method calls that exist as a key part of a recursive method may have an effect on the memory overhead of the application, especially when the recursive function is performed a large amount of times. In addition, there may be situations where one does not work at all. Overall, the choice between the two would depend on what they are being utilized for.

Where is Recursion Used?

One area where recursion is used over iteration is in languages such as Haskell that use the functional programming paradigm, because within this paradigm, according to Akhmechet (2006), variables are non-mutable constants (that is, they are set on creation and cannot be changed). This means that iterative looping will not function (as there is no state to change each time the loop runs), which means in turn that recursion can be used for the same effect. As there are certain benefits to languages that use these paradigms – they are easier to code and debug, as there are no issues of variables being changed and causing exceptions; they are easier to adapt to a multi-threaded environment as the compiler will adapt and make sections of the application concurrent where possible.

Another situation where recursion is used is in binary search trees (these are a subset of normal binary trees – the difference is that in a binary search tree, the values are ordered, whereas they may not be in a normal binary tree. Binary search trees are also known as ordered binary trees for this reason). In their simplest form, these use recursion to find a given result in a set of ordered values. For instance, for a set of numbers from one to ten, each step would select the middle number and check if the sought after result is greater or less than the middle number, which will half the possible results. It will do this again with the half that includes the sought after value, recursively repeating the task until it reaches the sought after value.

Real World Applications: Quicksort

One real world application of recursive techniques is an algorithm known as Quicksort created by Tony Hoare. Quicksort is an algorithm that is used to place objects (which may be variables, files or something else entirely) in a set order. First, Quicksort selects an element that will be known as the “pivot”, which it then puts into the correct place with all the objects lower than it to one side and all the objects greater than it on the other. This allows it to, similar to a binary search tree, split the objects into two sets, which it can then sort. This is known as divide-and-conquer, because it means that for the majority of the sorting, the set of data to sort within is smaller. According to Sedgewick (1978), Quicksort “has been shown to perform well in a variety of situations.”

created by Tony Hoare. Quicksort is an algorithm that is used to place objects (which may be variables, files or something else entirely) in a set order. First, Quicksort selects an element that will be known as the “pivot”, which it then puts into the correct place with all the objects lower than it to one side and all the objects greater than it on the other. This allows it to, similar to a binary search tree, split the objects into two sets, which it can then sort. This is known as divide-and-conquer, because it means that for the majority of the sorting, the set of data to sort within is smaller. According to Sedgewick (1978), Quicksort “has been shown to perform well in a variety of situations.”

Thus, this algorithm can be used in a variety of real world situations where someone has a list of objects that need to be sorted – for instance, a list of times for a race that contains many contestants, such as a marathon.

Conclusion

In conclusion, recursion is a useful tool for many programming paradigms and can be used to solve many tasks – in some cases, it should be compared to iteration in order to choose the correct method, while in other cases, like languages that use the functional paradigm where variables cannot be changed, it is the best or even the only choice.


References

Bibliography