- Computers & Software
Why Programming paradigms and languages?
Defining a Paradigm
A paradigm is defined as “a pattern or model” (Oxford 2012), in terms of programming, a paradigm can be said to serve as a pattern that represents a school of thought (Nomark 2012).
Recursion is a paradigm that is defined as a “function that calls itself” (FOLDOC 1996), notably however, when a recursive method is called, it is actually only capable of solving the simplest (and smallest) version of the problem at hand (known as the base case); recursion occurs when the problem in hand is larger than the base case, in this instance, the problem is split into two parts, one which the method can compute, and another which it cannot; the function then calls itself to work on the latter, and so on (Deitel et al. 2011).
The Academic Problem with Recursion
M.C. Escher’s Drawing hands (Figure 1) is seemingly referenced as an illustration of the basic concept of recursion within computer science (Clark and Feng 1985, Price 2012); however, this arguably only demonstrates the concept of self creation, and not the fundamental rule that recursion solves problems through lesser, identical instances of the same problem (Graham et al 1994); and is arguably more suitably illustrated by figure 2.
This notion is arguably supported by Hofstadter’s (1979) discussion of ‘Drawing Hands’, in the literature, Gödel, Escher, Bach: An Eternal Golden Braid; the concept of self creation within recursion is defined as “the series of stages that constitute the cycling-around… is a shift from one level of abstraction… to another…the successive “upward” shifts turn out to give rise to a closed cycle” (Hofstadter 2007: Pg. 101-102).
To exemplify recursion in a simple program, the following code returns the values of the ‘words’ array; it does so by taking the ‘words’ array as a parameter, and checking if the array size is zero, as it is not, it returns the first value, along with a comma to the new (‘test’) array; the program terminates only when all values are returned; the highlighted code shows the function recursively calling itself (Staskiewicz 2010).
How recursion works
This example re-emphasises that recursion is not self-referencing in, and of its entirety, it is instead a reference to a simplified version of itself; in this example, this would be a singular value of the complete function (e.g. one value of the words array; However, this particular example may highlight the further problem within the teachings of recursion, of the utilisation of unsuitable examples of programs to demonstrate its role.
For example, many computer-science text books utilise examples of recursion that involve Fibonacci numbers or factorials, when in actuality iteration would often be a more suitable solution (McConnell 2004), this common error is arguably understandable, as any recursive algorithm can be expressed non-recursively (Kruse 1987).
Figures 4 and 5 demonstrate a recursive and an iterative solution to a factorial respectively; the former has a slower performance, results in unpredictable run-time memory and additionally is harder to understand (McConnell 2004: pg.144), examples such as these reinforce the misguided notion that all recursive programs, compared to their non-recursive counterparts, are slower, and therefore inferior (Noble 2003); however this example is representative of the fact that recursion code is comparable more compact (Kernighan and Ritchie,1988, Skliarova and Sklyarov 2009).
The problem highlighted in the clarity of teaching recursion and its applications are supportive of the argument that recursion is one of the most challenging concepts to teach” (Gal-Ezer and Harel 1998); consequently, much has been researched and documented to address this issue, with various suggestions for solutions, over a considerable period of time, seemingly demonstrating the persistence of the problem.
Suggested solutions include teaching that is focussed on cognitive learning styles (Cheng-Chi et al. 1998), simulation (Kurtz and Johnson 1985) and based on various visualisations (Dann et al. 2001, Milne and Rowe 2002).
Given that a paradigm should aid in programming, it could be argued that the practicality of recursion as a paradigm is impaired by its difficulty of understanding, however, as McConnell (2004) contends, although recursion is often misrepresented and not commonly employed, when recursion is applied to certain problems, it can produce effective solutions to complex problems.
Recursion and it’s (suitable) Applications
Fractal is defined as “a curve or geometrical figure, each part of which has the same statistical character as the whole” (Oxford Dictionary 2012), likewise, “landscapes are self-similar... looking at a … it exhibits the same basic characteristics at every scale” (Kareem 2008: Pg. 128); as such, the simulation of a Landscape lends itself to creation by recursion.
Recursive construction of a mountain
Figure 7 demonstrates a raising of midpoints (midpoint displacement) from an original triangle shape to create a mesh, the process is recursively called to create an entire mountain range, as previously illustrated by figure 6.
Recursive construction of a River
Figure 9 demonstrates the subdivision of three mesh triangles (the creation of which is demonstrated by figure 8) during the curved line construction. Figure 10 demonstrates the process by first, second and third level of recursion (Prusinkiewicz and Hammel 1993).
Additional specific examples of recursive applications include number to character screen print, Compiler parsing (Kernighan and Ritchie,1988) and Quicksort (Hoare, 1962); in short, utilisations of recursion range “from mathematics to text processing and data structure manipulation” (Schuller 2006).
The basic definition of a programming language is described as “a set of rules, words, etc. that are used for writing computer programs” (Cambridge Dictionary 2011); as of 1972 there were approximately 200 higher level languages (Sammet 1972), and as such the current amount is almost certainly innumerable, this is despite failed efforts to create a single programming language UNCOL (Conway, 1958), PL/I (IBM, 1966) and ADA (Ichbiah, 1983); the sheer number of languages emphasises that the question to be addressed is not why they exist, but why so many exist and what factors influences their respective utilisations.
The popularity of languages has been dominated “in turn [by]…Fortran, Cobol, Basic, C, C++, and Java” (Derk 2011: Pg. 163), the former two languages were utilised by contrasting sectors; COBOL was employed for Business Data Processing, and FORTRAN for scientific purposes (Sammet 1972), indeed the choice of programming language is influenced by the task in hand, but further factors such as the project’s platform, speed of creation and execution, readability, support and ease of debugging impact upon language choice (Reghunadh and Jain 2011); furthermore compounding factors such as the initial language learnt by a programmer, may additionally influence choice of programming language (Price-Jones et al. 1993 ).
Recursion and Programming Languages
Virtually all current programming languages provide support for recursion (Skliarova, and Sklyarov 2009), that said however certain languages do give preference to iterative looping constructs (such as Java and C [Gibbons and Oliveira 2009]) over recursion; solutions such as the removing of tail recursion (Bailey and Weston 2001) and conversion of recursive methods to iterative recursion (Schuller 2006) have been suggested as possible methods to compensate for this iterative preference.
Paradigms exist in order to aid programmers in their efforts, although elements of the academic teaching of recursion, coupled with the apparent complexity of recursion as a concept, arguably impair recursion as an effective paradigm.
The vast array of programming languages is representative of the broad scope of problems programs are tasked with, and although languages differ in speed, readability, support, and ease of debugging, there are certainly optimal languages for certain tasks.
The attempts to address issues regarding the concept of recursion, and additionally issues with the compatibility of mainstream languages in relation to recursion are testament to the value of both respectively.