Java Recursion

11 Key excerpts on "Java Recursion"

• 

  No longer available |Learn more

  Algorithm and Data Structure (Concepts & Applications)

  • (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.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structures and Algorithms in Java

  • 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.

  Sign up to read

  Learn more about book
• 

  No longer available |Learn more

  Programming Essentials Using Java

  A Game Application Approach

  • William McAllister, S. Jane Fritz(Authors)
  • 2017(Publication Date)
  • Mercury Learning and Information

    (Publisher)

  Figure 9.1 illustrates both of these forms of recursion.

  In mathematics, recursion is often used to define functions and series that can also be defined without using recursion. For example, a non-recursive definition of ten factorial (10!) is: 10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

  This non-recursive definition of 10! can be generalized to a non-recursive definition of n! for any positive value of n.

  Definition

  The non-recursive definition of n! for values of n ≥ 0

  n! ≡ n * (n - 1) * (n - 2) * (n – 3) * (n – 4)* ....* 3 * 2 * 1 and 0! ≡ 1

  Alternately, the definition of 10! can be more succinctly stated recursively as

  10! ≡ 10 * (10 - 1)! and 0! ≡ 1

  This recursive definition can be generalized to a recursive definition of n! for any positive value of n.

  Definition

  The recursive definition of n!

  n! ≡ n * (n - 1)! and 0! ≡ 1

  The equivalence of the recursive and non-recursive definitions can be easily understood by examining the non-recursive definition of 10! and 9!

  The last nine terms in the equation for 10! are contained in the right side of the equation for 9!, so 10! can certainly be expressed as 10 * 9!, which is the recursive definition of 10!. Having been shown this example, most of us would accept the fact that 9! can be used to calculate 10!, that is:

  10! = 10 * 9!

  This is the recursive way of calculating 10! which we now understand because we have realized that 9! = 9* 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1. In effect, we have used the non-recursive definition of 9! to understand the recursive definition of 10!.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Objects, Abstraction, Data Structures and Design

  Using C++

  • Elliot B. Koffman, Paul A. T. Wolfgang(Authors)
  • 2012(Publication Date)
  • Wiley

    (Publisher)

  C h a p t e r O b j e c t i v e s ◆ To understand how to think recursively ◆ To learn how to trace a recursive function ◆ To learn how to write recursive algorithms and functions for searching arrays ◆ To understand how to use recursion to solve the Towers of Hanoi problem ◆ To understand how to use recursion to process two-dimensional images ◆ To learn how to apply backtracking to solve search problems such as finding a path through a maze 403 Recursion C h a p t e r 7 T his chapter introduces a programming technique called recursion and shows you how to think recursively. You can use recursion to solve many kinds of programming problems that would be very difficult to conceptualize and solve without recursion. Computer scientists in the field of artificial intelligence (AI) often use recursion to write programs that exhibit intelligent behavior: playing games such as chess, proving mathematical theorems, recognizing patterns, and so on. In the beginning of the chapter you will be introduced to recursive thinking and how to design a recursive algorithm and prove that it is correct. You will also learn how to trace a recursive function and use activation frames for this purpose. Recursive algorithms and functions can be used to perform common mathe- matical operations such as computing a factorial or a greatest common divisor. Recursion can be used to process familiar data structures such as strings, arrays, and linked lists and to design a very efficient array search technique called binary search. Recursion can be used to solve a variety of other problems. The case studies in this chapter use recursion to solve a game, to search for “blobs” in a two- dimensional image, and to find a path through a maze. 7.1 Recursive Thinking Recursion is a problem-solving approach that can be used to generate simple solu- tions to certain kinds of problems that would be difficult to solve in other ways.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structures

  Abstraction and Design Using Java

  • Elliot B. Koffman, Paul A. T. Wolfgang(Authors)
  • 2021(Publication Date)
  • Wiley

    (Publisher)

  C h a p t e r 213 Recursion T his chapter introduces a programming technique called recursion and shows you how to think recursively. You can use recursion to solve many kinds of programming prob- lems that would be very difficult to conceptualize and solve without recursion. Com- puter scientists in the field of artificial intelligence (AI) often use recursion to write programs that exhibit intelligent behavior: playing games such as chess, proving mathematical theo- rems, recognizing patterns, and so on. In the beginning of the chapter, you will be introduced to recursive thinking and how to design a recursive algorithm and prove that it is correct. You will also learn how to trace a recursive method and use activation frames for this purpose. Recursive algorithms and methods can be used to perform common mathematical operations, such as computing a factorial or a greatest common divisor (gcd). Recursion can be used to process familiar data structures, such as strings, arrays, and linked lists, and to design a very efficient array search technique called binary search. You will also see that a linked list is a recursive data structure and learn how to write recursive methods that perform common list-processing tasks. Recursion can be used to solve a variety of other problems. The case studies in this chapter use recursion to solve a game, to search for “blobs” in a two-dimensional image, and to find a path through a maze. 5 C h a p t e r O b j e c t i v e s ◆ To understand how to think recursively ◆ To learn how to trace a recursive method ◆ To learn how to write recursive algorithms and methods for searching arrays ◆ To learn about recursive data structures and recursive methods for a LinkedList class ◆ To understand how to use recursion to solve the Towers of Hanoi problem ◆ To understand how to use recursion to process two-dimensional images ◆ To learn how to apply backtracking to solve search problems such as finding a path through a maze

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Introduction to Computing Using Python

  An Application Development Focus

  • Ljubomir Perkovic(Author)
  • 2012(Publication Date)
  • Wiley

    (Publisher)

  CHAPTER 10 Recursion 10.1 Introduction to Recursion 352 10.2 Examples of Recursion 358 10.3 Run Time Analysis 367 10.4 Searching 374 10.5 Case Study: Tower of Hanoi 379 Chapter Summary 385 Solutions to Practice Problems 385 Exercises 387 Problems 388 IN THIS CHAPTER, we learn 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 make use of recursion in this chapter’s case study to develop a tool to solve, and visualize the solution to, the Tower of Hanoi problem. We also use recursion in Chapter 10 when developing web crawlers. 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. 351 352 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 approach to problem solving. In the next section, we apply recursive thinking and how to develop recursive functions. Recursive Functions Here is an example that illustrates what we mean by a function that calls itself: Module: ch10.py 1 def countdown(n): 2 print(n) 3 countdown(n-1) In the implementation of function countdown(), the function countdown() is called.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Discrete Mathematics with Applications

  • 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

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structures and Algorithms in Python

  • 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.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Quick Recursion

  • David Matuszek(Author)
  • 2023(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Chapter 1 Understanding Recursion

  DOI: 10.1201/9781003359616-1

  1.1 A Note on Languages

  Any programming book needs examples, and examples have to be in some language.

  This book uses two well-known languages, Java and Python 3. The code is kept simple, without any language-specific “tricks,” so it should be accessible even to programmers who know neither of these languages.

  That said, it is impossible to avoid all language-specific features and still have working code. Python uses indentation to show nesting of statements, while Java uses braces. To remove leading blanks, Python uses strip() while Java uses trim() . Differences such as these should not greatly obscure the examples.

  1.2 Recursive Definitions

  A recursive definition is a definition in which the thing being defined occurs as part of its own definition.

  Sounds circular, doesn’t it? Circular definitions, in computer science as elsewhere, are valueless and should be avoided. The distinction between a recursive and a circular definition lies in the use of the work “part.” Any recursive definition has two parts:

  1. a noncircular part, or basis, which is like an ordinary definition, and directly specifies some objects that fit the definition; and
  2. a recursive (circular) part, which allows you to use the objects that fit the definition in determining whether new objects also fit the definition.

  Some examples should clarify these ideas. Here is an ordinary definition:

  Vowel: one of the letters “a,” “e,” “i,” “o,” “u,” or “y.”

  Clearly, there are exactly six things that fit the above definition of a vowel. Now consider the following circular definition:

  Yowl: any yowl followed by a vowel.

  By this definition, any yowl followed by a vowel is also a yowl; thus, if we could find one thing which is a yowl, then any things formed by adding vowels to that yowl would themselves be yowls. The problem is in finding that first yowl. Since we have no place to start, the definition is circular, and valueless.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  C++ 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.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  C++ Programming

  From Problem Analysis to Program Design

  • D. Malik(Author)
  • 2017(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  Recursion IN THIS CHAPTER, YOU WILL: 1. Learn about recursive definitions 2. Explore the base case and the general case of a recursive definition 3. Discover what a recursive algorithm is 4. Learn about recursive functions 5. Become familiar with direct and indirect recursion 6. Explore how to use recursive functions to implement recursive algorithms 7. Become aware of recursion vs. iteration 15 CHAPTER © HunThomas/Shutterstock.com Copyright 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. 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. 1036 | Chapter 15: Recursion In previous chapters, to devise solutions to problems, we used the most common technique called iteration. For certain problems, however, using the iterative tech- nique to obtain the solution is quite complicated. This chapter introduces another problem-solving technique called recursion and provides several examples demon- strating how recursion works. Recursive Definitions The process of solving a problem by reducing it to smaller versions of itself is called recursion. Recursion is a very powerful way to solve certain problems for which the solution would otherwise be very complicated. Let us consider a problem that is familiar to most everyone. In mathematics, the factorial of a nonnegative integer is defined as follows: 0! 1 5 (15-1) ! ( 1)! if 0 5 3 2 . n n n n (15-2) In this definition, 0! is defined to be 1, and if n is an integer greater than 0, first we find ( 1)! 2 n and then multiply it by n. To find ( 1)! 2 n , we apply the definition again. If ( 1) 0 2 . n , then we use Equation 15-2; otherwise, we use Equation 15-1.

  Sign up to read

  Learn more about book