# Recursion

Solo disponible en BuenasTareas
• Páginas : 7 (1521 palabras )
• Descarga(s) : 0
• Publicado : 12 de noviembre de 2011

Vista previa del texto
THE DYNAMICS OF RECURSION

The Dynamics of Recursion
1. Introduction
Recursion was primarily considered to be used for analog calculations; however, it has been later used to obtain analog illustration of classical calculation complexity classes. In the context of this research, the examination will be the dynamics of recursion and the fundamental uses of the varying recursivefunctions. The ideal purpose is to provide an overall generalized understanding with sufficient function examples as they apply to programming and the algorithmic logic, which demonstrate the recursive objective one is trying to achieve. In demonstrating recursion, it is the intentions of this report to breakdown the varying methods in such a way it makes it easily understandable for debugging recursivesubprograms. First, discussing the origin and how it is linked to modern day computing. Second, explain the functions of recursion and its algorithmic logic. Lastly, the report will examine the instances where recursion is not the most efficient method.
2. Origin of Recursion
Recursion refers to several related concepts in mathematics and logic, the origins of which date back muchfurther than modern computing. However, “the systematic study of recursion began in the 1920’s when mathematical logic began to treat questions of definability, computability, and decidability” (Ralston, 2000, p. 1507). The formulation of recursive functions and its theories can be directly linked to the works of Alonzo Church, Kurt Gödel, Stephen Kleene, and Alan Turing. During the 1930s, theforenamed mathematicians published papers dealing with the theories of computation and the tasks involved with solving complex problems, which seemed unsolvable. Kurt Gödel delivered a series of lectures on the newly developed mathematical logic called “general recursive function” that he can be attributed.
Kurt Gödel took the work of Alan Turing and Alonzo Church and demonstrated it wasimpossible to capture a portion of the mathematical logic as it relates to the Halting Problem. In turn, he demonstrated the limitations of the axiomatic method. The proof can be read in Gödel’s Incompleteness Theorem. In his paper Gödel stated, “any sufficiently rich axiomatic system contains undecidable but nonetheless true propositions” (Ralston, Reilly, & Hemmendinger, 2000, p. 1813). Thewidespread acceptances of Gödel’s theory, lead to the idea of “general recursive functions.” Therefore, the emergence of computers and software programming became second nature to use recursive function calculations through high-level languages based exclusively on these published papers. In the 1950s, developing algorithms for solving computer programs became a powerful technique and a significantmilestone for the computer science field.
3. Description of Recursion
Recursion is a powerful logic algorithm that has provided some rather simple solutions to complex problems. It emerges during our daily lives quite often. Have you ever discussed the origin of the chicken and the egg? On the other hand, have you ever been awaken from a dream only to discover that you were stilldreaming? In order to understand recursion you must first understand recursion. A common method of solving a large problem is to break it down into smaller problems that can be solved rather easily. The solutions to the smaller problem are then combined to generate the solution to the original, larger problem. A recursive function consists of two parts: the base case and the general case (Malik,2004). Here is the basic format of a recursive function:

returnType recursiveFunction(argument)
{
if (Boolean expression) // this is the base case
return 1;
return recursiveFunction(argument – 1); // the general case
}
When developing a recursive function, it is essential to define the base case. The base case is the most important piece of recursion....