Computer Science
Recursion Programming
Recursion programming is a technique in which a function calls itself repeatedly until a specific condition is met. It is commonly used in solving problems that can be broken down into smaller sub-problems. Recursion can be a powerful tool for solving complex problems, but it requires careful design to avoid infinite loops.
Written by Perlego with AI-assistance
Related key terms
1 of 5
8 Key excerpts on "Recursion Programming"
No longer available |Learn more- (Author)
- 2014(Publication Date)
- Learning Press(Publisher)
________________________ WORLD TECHNOLOGIES ________________________ Chapter 4 Recursion & Parallel Algorithm Recursion (computer science) Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem. The approach can be applied to many types of problems, and is one of the central ideas of computer science. The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions. Most high-level computer programming languages support recursion by allowing a function to call itself within the program text. Some functional programming languages do not define any looping constructs but rely solely on recursion to repeatedly call code. Computability theory has proven that these recursive-only languages are mathematically equivalent to the imperative languages, meaning they can solve the same kinds of problems even without the typical control structures like “while” and “for”. Tree created using the Logo programming language and relying heavily on recursion. ________________________ WORLD TECHNOLOGIES ________________________ Recursive data types Many computer programs must process or generate an arbitrarily large quantity of data. Recursion is one technique for representing data whose exact size the programmer does not know: the programmer can specify this data with a self-referential definition. There are two flavors of self-referential definitions: inductive and coinductive definitions. Inductively-defined data An inductively-defined recursive data definition is one that specifies how to construct instances of the data.
eBook - PDFIntroduction to Computing Using Python
An Application Development Focus
- Ljubomir Perkovic(Author)
- 2015(Publication Date)
- Wiley(Publisher)
CHAPTER 10 Recursion 10.1 Introduction to Recursion 330 10.2 Examples of Recursion 336 10.3 Run Time Analysis 347 10.4 Searching 354 Case Study: Tower of Hanoi 359 Chapter Summary 360 Solutions to Practice Problems 360 Exercises 362 Problems 363 IN THIS CHAPTER, we learn about recursion, a powerful problem-solving technique, and run time analysis. Recursion is a problem-solving technique that expresses the solution to a problem in terms of solutions to subproblems of the original problem. Recursion can be used to solve problems that might otherwise be quite challenging. The functions developed by solving a problem recursively will naturally call themselves, and we refer to them as recursive functions. We also show how namespaces and the program stack support the execution of recursive functions. We demonstrate the wide use of recursion in number patterns, fractals, virus scanners, and searching. We differentiate between linear and nonlinear recursion and illustrate the close relationship between iteration and linear recursion. As we discuss when recursion should and should not be used, the issue of program run time comes up. So far we have not worried much about the efficiency of our programs. We now rectify this situation and use the opportunity to analyze several fundamental search tasks. We develop a tool that can be used to analyze experimentally the running time of functions with respect to the size of the input. 329 330 Chapter 10 Recursion 10.1 Introduction to Recursion A recursive function is a function that calls itself. In this section we explain what this means and how recursive functions get executed. We also introduce recursive thinking as an ap- proach to problem solving. In the next section, we apply recursive thinking and how to develop recursive functions.
eBook - PDF- Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser(Authors)
- 2014(Publication Date)
- Wiley(Publisher)
Chapter 5 Recursion Contents 5.1 Illustrative Examples . . . . . . . . . . . . . . . . . . . . . . 191 5.1.1 The Factorial Function . . . . . . . . . . . . . . . . . . . 191 5.1.2 Drawing an English Ruler . . . . . . . . . . . . . . . . . . 193 5.1.3 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . 196 5.1.4 File Systems . . . . . . . . . . . . . . . . . . . . . . . . . 198 5.2 Analyzing Recursive Algorithms . . . . . . . . . . . . . . . 202 5.3 Further Examples of Recursion . . . . . . . . . . . . . . . . 206 5.3.1 Linear Recursion . . . . . . . . . . . . . . . . . . . . . . . 206 5.3.2 Binary Recursion . . . . . . . . . . . . . . . . . . . . . . 211 5.3.3 Multiple Recursion . . . . . . . . . . . . . . . . . . . . . 212 5.4 Designing Recursive Algorithms . . . . . . . . . . . . . . . 214 5.5 Recursion Run Amok . . . . . . . . . . . . . . . . . . . . . 215 5.5.1 Maximum Recursive Depth in Java . . . . . . . . . . . . . 218 5.6 Eliminating Tail Recursion . . . . . . . . . . . . . . . . . . 219 5.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 190 Chapter 5. Recursion One way to describe repetition within a computer program is the use of loops, such as Java’s while-loop and for-loop constructs described in Section 1.5.2. An entirely different way to achieve repetition is through a process known as recursion. Recursion is a technique by which a method makes one or more calls to itself during execution, or by which a data structure relies upon smaller instances of the very same type of structure in its representation. There are many examples of recursion in art and nature. For example, fractal patterns are naturally recursive. A physical example of recursion used in art is in the Russian Matryoshka dolls. Each doll is either made of solid wood, or is hollow and contains another Matryoshka doll inside it. In computing, recursion provides an elegant and powerful alternative for per- forming repetitive tasks.
eBook - PDF- Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser(Authors)
- 2013(Publication Date)
- Wiley(Publisher)
Chapter 4 Recursion Contents 4.1 Illustrative Examples . . . . . . . . . . . . . . . . . . . . . . 150 4.1.1 The Factorial Function . . . . . . . . . . . . . . . . . . . 150 4.1.2 Drawing an English Ruler . . . . . . . . . . . . . . . . . . 152 4.1.3 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . 155 4.1.4 File Systems . . . . . . . . . . . . . . . . . . . . . . . . . 157 4.2 Analyzing Recursive Algorithms . . . . . . . . . . . . . . . 161 4.3 Recursion Run Amok . . . . . . . . . . . . . . . . . . . . . 165 4.3.1 Maximum Recursive Depth in Python . . . . . . . . . . . 168 4.4 Further Examples of Recursion . . . . . . . . . . . . . . . . 169 4.4.1 Linear Recursion . . . . . . . . . . . . . . . . . . . . . . . 169 4.4.2 Binary Recursion . . . . . . . . . . . . . . . . . . . . . . 174 4.4.3 Multiple Recursion . . . . . . . . . . . . . . . . . . . . . 175 4.5 Designing Recursive Algorithms . . . . . . . . . . . . . . . 177 4.6 Eliminating Tail Recursion . . . . . . . . . . . . . . . . . . 178 4.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 149 One way to describe repetition within a computer program is the use of loops, such as Python’s while-loop and for-loop constructs described in Section 1.4.2. An entirely different way to achieve repetition is through a process known as recursion. Recursion is a technique by which a function makes one or more calls to itself during execution, or by which a data structure relies upon smaller instances of the very same type of structure in its representation. There are many examples of recursion in art and nature. For example, fractal patterns are naturally recursive. A physical example of recursion used in art is in the Russian Matryoshka dolls. Each doll is either made of solid wood, or is hollow and contains another Matryoshka doll inside it. In computing, recursion provides an elegant and powerful alternative for per- forming repetitive tasks.
eBook - PDFC++ Programming
Program Design Including Data Structures
- D. Malik(Author)
- 2017(Publication Date)
- Cengage Learning EMEA(Publisher)
3. The base case stops the recursion. The concept of recursion in computer science works similarly. Here, we talk about recursive algorithms and recursive functions. An algorithm that finds the solution to a given problem by reducing the problem to smaller versions of itself is called a recursive algorithm . The recursive algorithm must have one or more base cases, and the general solution must eventually be reduced to a base case. A function that calls itself is called a recursive function . That is, the body of the recursive function contains a statement that causes the same function to execute again before com-pleting the current call. Recursive algorithms are implemented using recursive functions. Next, let us write the recursive function that implements the factorial function. int fact( int num) { if (num == 0) return 1; else return num * fact(num - 1); } Figure 15-1 traces the execution of the following statement: cout << fact(3) << endl; FIGURE 15-1 Execution of fact(3) because num != 0 return 3 * fact(2); fact(3) because num != 0 return 2 * fact(1); fact(2) because num != 0 return 1 * fact(0); fact(1) because num is 0 return 1; fact(0) return 1 fact(0) = 1 return 1 * 1 fact(1) = 1 return 2 * 1 fact(2) = 2 return 3 * 2 fact(3) = 6 3 num 2 num 1 num 0 num Copyright 2018 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-300 1054 | Chapter 15: Recursion The output of the previous cout statement is: 6 In Figure 15-1, the down arrow represents the successive calls to the function fact , and the upward arrows represent the values returned to the caller, that is, the calling function. Let us note the following from the preceding example, involving the factorial function. ? Logically, you can think of a recursive function as having an unlimited number of copies of itself. ? Every call to a recursive function—that is, every recursive call—has its own code and its own set of parameters and local variables.
eBook - PDF- Thomas Koshy(Author)
- 2004(Publication Date)
- Academic Press(Publisher)
Chapter 5 Recursion It is common sense to take a method and try it. If it fails, admit it frankly and try another. But above all, try something. — FRANKLIN ROOSEVELT R ecursion is an elegant and powerful problem-solving technique, used extensively in both discrete mathematics and computer science. Many programming languages, such as ALGOL, FORTRAN 90, C++, and Java, support recursion. This chapter investigates this powerful method in detail. In addition, we will study three simple methods for solving recurrence relations: iteration, characteristic equations, and generating functions. We also will establish the validity of recursive algorithms using induction and analyze their complexities using the big-oh and big-theta notations. Some of the interesting problems we pursue in this chapter are: • There are three pegs X, Y, and Z on a platform and 64 disks of increasing sizes at X. We would like to move them from X to Z using Y as an auxiliary peg subject to the following conditions: Only one disk can be moved at a time. No disk can be placed on the top of a smaller disk. If it takes one second to transfer a disk from one peg to another, how long will it take to solve the puzzle? • Is there a formula for the number of n -bit words containing no two consecutive 1’s? • Suppose we introduce a mixed pair (male and female) of 1-month-old rabbits into a large enclosure on January 1. By the end of each month, the rabbits become mature, and each pair produces k − 1 mixed pairs of offspring at the beginning of the following month. Find the average age of the rabbit pairs at the beginning of the n th month. • Can we estimate the number of divisions required to compute gcd { a , b } by the euclidean algorithm? • What is a divide-and-conquer algorithm? If f ( n ) denotes the number of operations required by such an algorithm, what can you say about its order of complexity? 261
eBook - PDF- L.E. Sanchis(Author)
- 1992(Publication Date)
- North Holland(Publisher)
We discuss the manner in which calling algorithms are written and executed in the well-known language of locations involving locations X O , X I , . . ., and each location contains numerical values that change during the computation. The execution of a recursive algorithmobviously depends on the manner in which the instructions are executed. While the explicit instructions are independent of the algorithm in which they appear, in the sense that they can be executed without reference to any algorithm in the system, a call instruction involves one or more algorithms. This is basically a recursive relation that we must take as a primitive. We describe the execution of recursive F-algorithms in a system A in terms of two ideal entities: one that we call the computing A-machine, and another that we call the 3-oracle. 112 L.E. Sanchis The computing machine is a recursive machine and it has two different but related types of actions. First, the machine executes instructions during a compu- tation involving a particular algorithm. In general, these instructions are explicit or calls involving algorithms in the system. Second, the computing machine computes algorithms with a given input and returns a value whenever the computation is defined. The machine is recursive in the sense that the execution of algorithms requires the execution of instructions, and the execution of instructions requires the execu- tion of algorithms. We propose this as a primitive computational concept in order to formulate the extended Church’s thesis. On the other hand, if we work in the context of a given formalization, given by a formal machine or formal programming language, the recursive computation described above can be formalized, usually via some definition by induction. This is a well known phenomenon where, for exam- ple, the computation of a Turing machine can be formalized, although the notion of machine computation in general cannot be formalized.
eBook - PDFC++ Programming
From Problem Analysis to Program Design
- D. Malik(Author)
- 2017(Publication Date)
- Cengage Learning EMEA(Publisher)
Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. Problem Solving Using Recursion | 1039 1 5 execute an infinite recursive function on a computer, the function executes until the system runs out of memory and results in an abnormal termination of the program. Recursive functions (algorithms) must be carefully designed and analyzed. You must make sure that every recursive call eventually reduces to a base case. This chapter pro- vides several examples that illustrate how to design and implement recursive algorithms. To design a recursive function, you must do the following: a. Understand the problem requirements. b. Determine the limiting conditions. For example, for a list, the limiting condition is the number of elements in the list. c. Identify the base cases and provide a direct solution to each base case. d. Identify the general cases and provide a solution to each general case in terms of smaller versions of itself. Problem Solving Using Recursion Examples 15-1 through 15-3 illustrate how recursive algorithms are developed and implemented in C++ using recursive functions. EXAMPLE 15-1 LARGEST ELEMENT IN AN ARRAY In Chapter 8, we used a loop to find the largest element in an array. In this example, we use a recursive algorithm to find the largest element in an array. Consider the list given in Figure 15-2. The largest element in the list in Figure 15-2 is 10. Suppose list is the name of the array containing the list elements. Also, suppose that list[a]...list[b] stands for the array elements list[a], list[a + 1], ..., and list[b]. For example, list[0]...list[5] represents the array elements list[0], list[1], list[2], list[3], list[4], and list[5].
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
