Java Recursion

9 Key excerpts on "Java Recursion"

• 

  eBook - ePub

  Mastering JavaScript Functional Programming

  Write clean, robust, and maintainable web and server code using functional JavaScript, 2nd Edition

  • Federico Kereki(Author)
  • 2020(Publication Date)
  • Packt Publishing

    (Publisher)

  a function calls itself again and again, until it doesn't . Recursion is a natural technique for several kinds of problems, such as the following:

  • Mathematical definitions, such as the Fibonacci sequence or the factorial of a number.
  • Data-structure-related algorithms, with recursively defined structures, such as lists (a list is either empty or consists of a head node followed by a list of nodes) or trees (a tree might be defined as a special node, called the root, linked to zero or more trees).
  • Syntax analysis for compilers, based on grammar rules, which themselves depend on other rules, which also depend on other rules, and so on.
  • And many more! It even appears in art and humor, as shown in the following screenshot:

  Google itself jokes about it: if you ask about recursion, it answers "Did you mean: recursion!"

  In any case, a recursive function, apart from some easy, base cases, in which no further computation is required, always needs to call itself one or more times in order to perform part of the required calculations. This concept may be not very clear at the moment, so, i n the following sections, we will see how we can think in a recursive fashion and then solve several common problems by applying this technique .

  Passage contains an image

  Thinking recursively

  The key to solving problems recursively is assuming that you already have a function that does whatever you need and just calling it normally. (Doesn't this sound weird? Actually, it is quite appropriate: if you want to solve a problem by using recursion, you must first have solved it before...) On the other hand, if you try to work out in your head how the recursive calls work and attempt to follow the flow in your mind, you'll probably just get lost. So what you need to do is the following:

  1. Assume you already have an appropriate function to solve your problem.
  2. See how the big problem can be solved by solving one (or more) smaller problems.
  3. Solve those problems by using the imagined function from step 1.
  4. Decide what your base cases 

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  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 - ePub

  Learning and Awareness

  • Ference Marton, Shirley Booth(Authors)
  • 2013(Publication Date)
  • Routledge

    (Publisher)

  Then there is a return to a normal state by reversing the process. Recursion is a construct which, as far as it occurs in programmed algorithms, allows the programmer to bring about repetition, in a rather special way compared to the more usual (or, one might say, in other older programming environments) iterative method of looping through instructions until a specified condition is met. For example, a number of cycles has been made, or a required state is reached, or a particular item has been found in the data, or time runs out. To write such a looping algorithm in a program it is necessary to define what should be done each time the cycle is performed and exactly what conditions should call a halt. Recursion, in contrast, is able to bring about repetition through the fundamental property of self-reference: A statement that is to be repeated makes use of itself in a more limited form—thereby getting repeated, until a previously specified terminating case is reached. The context in which the students in the study met recursion was as a way of writing ML functions that facilitate repetition, brought about by the defined function referring to itself, in an ever diminishing form, until a suitable criterion, or terminating case, is met (Booth, 1992b). As was mentioned in chapter 2, ML is grounded in mathematics, and recursion is directly equivalent to mathematical induction, an approach to proving a mathematical statement by assuming the truth of a similar statement and knowing that one instantiation of the statement is proven true. It should also be said that recursion, like mathematical induction, is a notoriously difficult concept for students to make sense of, and a good deal of research has gone into identifying ways of simplifying it for the learner (Anderson, Pirolli, & Farrell, 1988; Henderson & Romero, 1989)

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Mastering JavaScript Functional Programming

  Write clean, robust, and maintainable web and server code using functional JavaScript and TypeScript

  • Federico Kereki(Author)
  • 2023(Publication Date)
  • Packt Publishing

    (Publisher)

  are done.

  Recursion is a natural technique for several kinds of problems, such as the following:

  • Mathematical definitions, such as the Fibonacci sequence or the factorial of a number
  • Data-structure-related algorithms with recursively defined structures, such as lists (a list is either empty or consists of a head node followed by a list of nodes) or trees (a tree might be defined as a special node, called the root, linked to zero or more trees)
  • Syntax analysis for compilers based on grammar rules, which themselves depend on other rules, which also depend on other rules, and so on

  And many more! It even appears in art and humor, as shown in Figure 9 .1 :

  Figure 9.1 – Google itself jokes about it: if you ask about recursion, it answers, “Did you mean: recursion”

  Apart from some easy base cases in which no further computation is required, a recursive function must call itself one or more times to perform part of the required calculations. This concept may not be very clear at this point, so in the following sections, we will see how we can think recursively and solve several common problems by applying this technique.

  Thinking recursively

  The key to solving problems recursively is assuming that you already have a function that does whatever you need and just calling it. (Doesn’t this sound weird? Actually, it is quite appropriate: if you want to solve a problem with recursion, you must first have solved it before...) On the other hand, if you attempt to work out in your head how the recursive calls work and try to follow the flow, you’ll probably just get lost. So, what you need to do is the following:

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Essential Algorithms

  A Practical Approach to Computer Algorithms Using Python and C#

  • Rod Stephens(Author)
  • 2019(Publication Date)
  • Wiley

    (Publisher)

  CHAPTER 9 Recursion

  Recursion occurs when a method calls itself. The recursion can be direct (when the method calls itself) or indirect (when the method calls some other method that then calls the first method).

  Recursion can also be single (when the method calls itself once) or multiple (when the method calls itself multiple times).

  Recursive algorithms can be confusing because people don't naturally think recursively. For example, to paint a fence, you probably would start at one end and start painting until you reach the other end. It is less intuitive to think about breaking the fence into left and right halves and then solving the problem by recursively painting each half.

  However, some problems are naturally recursive. They have a structure that allows a recursive algorithm to easily keep track of its progress and find a solution. For example, trees are naturally recursive because branches divide into smaller branches that divide into still smaller branches and so on. For that reason, algorithms that build, draw, and search trees are often recursive.

  This chapter explains some useful algorithms that are naturally recursive. Some of these algorithms are useful by themselves, but learning how to use recursion in general is far more important than learning how to solve a single problem. Once you understand recursion, you can find it in many programming situations.

  Recursion is not always the best solution, however, so this chapter also explains how you can remove recursion from a program when recursion might cause poor performance.

  Basic Algorithms

  Some problems have naturally recursive solutions. The following sections describe several naturally recursive algorithms for calculating factorials, finding Fibonacci numbers, solving the rod-cutting problem, and moving disks in the Tower of Hanoi puzzle.

  These relatively straightforward algorithms demonstrate important concepts used by recursive algorithms. Once you understand them, you'll be ready to move on to the more complicated algorithms described in the rest of this chapter.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Foundations of Combinatorics with Applications

  • Edward A. Bender, S. Gill Williamson(Authors)
  • 2013(Publication Date)
  • Dover Publications

    (Publisher)

  PART III

  Recursion

  Recursive thinking plays a fundamental role in combinatorics, theoretical computer science and programming. The next chapter introduces the recursive approach and the following two chapters discuss important applications.

  Definition Recursive approach A recursive approach to a problem consists of two parts :

  • The problem is reduced to one or more problems of the same sort which are simpler in some sense.
  • There is a collection of simplest problems to which all others are reduced after one or more steps. A solution to these simplest problems is given.

  As you might expect, a recursive algorithm is one that refers to itself. This seemingly simple notion is extremely important. Recursive algorithms and their translation into recursive procedures and recursive data structures are fundamental in computer science. For example, here’s a recursive algorithm for sorting a list. (Sorting a list means putting the items in increasing order.)

  • divide the list roughly in half,
  • sort each half, and
  • “merge” the two sorted halves.

  Proof by induction and recursive algorithms are closely related. We’ll begin Chapter 7 by examining inductive proofs and recursive equations. Then we’ll look briefly at thinking and programming recursively.

  Suppose that we have some items that have a “natural” order; e.g., the natural order for student records might be

  • alphabetic by name (last name first),
  • first by class and, within a class, alphabetic by name, or
  • by grade point average with highest first.

  We may allow ties. The problem of sorting is as follows: Given a list of items in no particular order, rearrange it so that it is in its natural order. In the event of a tie, the relative order of the tied items is arbitrary. In Chapter 8, we’ll study some of the recursive aspects of software and hardware sorting algorithms. Many of these use the “divide and conquer” technique, which often appears in recursive algorithms. We end the chapter with a discussion of this important technique.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Introduction to Programming and Problem-Solving Using Scala

  • Mark C. Lewis, Lisa Lacher(Authors)
  • 2016(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Chapter 5 Recursion for Iteration 5.1    Basics of Recursion 5.2    Writing Recursive Functions 5.3    User Input 5.4    Abstraction Tail Recursive Functions 5.5    Matching

  match versus switch

  5.6    Bad Input, Exceptions, and the try/catch Expression

  5.7    Putting It Together 5.8    Looking Ahead 5.9    End of Chapter Material 5.9.1    Problem Solving Approach 5.9.2    Summary of Concepts 5.9.3    Self-Directed Study 5.9.4    Exercises 5.9.5    Projects

  Gaining conditionals provided us with a lot of power, we can express more complex logic in our code. Adding functions gave us the ability to break problems into pieces and reuse functionality without retyping code. There is still something very significant that we are missing. Currently, when we write a piece of code, it happens once. We can put that code into a function and then call the function over and over, but it will only happen as many times as we directly call it. We cannot easily vary the number of times that something happens, or make anything happen a really large number of times. This is a problem, because one of the things that computers are really good at is doing the same thing many times without getting bored or distracted. The is a capability that we really need to add to our toolbox. There is more than one way to make something happen multiple times in Scala. One of these ways, RECURSION , we can do with just functions and conditionals, constructs that we have already learned.

  5.1  Basics of Recursion

  Recursion is a concept that comes from mathematics. A mathematical function is recursive if it is defined in terms of itself. To see how this works, we will begin with factorial. You might recall from math classes that n! is the product of all the integers from 1 up to n. We might write this as n! = 1 * 2 * … * n

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Algorithms: Design Techniques And Analysis (Revised Edition)

  Design Techniques and Analysis(Revised Edition)

  • M H Alsuwaiyel(Author)
  • 2016(Publication Date)
  • WSPC

    (Publisher)

  PART 2 Techniques Based on Recursion

  This part of the book is concerned with a particular class of algorithms, called recursive algorithms . These algorithms turn out to be of fundamental importance and indispensible in virtually every area in the field of computer science. The use of recursion makes it possible to solve complex problems using algorithms that are concise, easy to comprehend, and efficient (from an algorithmic point of view). In its simplest form, recursion is the process of dividing the problem into one or more subproblems , which are identical in structure to the original problem and then combining the solutions of these subproblems to obtain the solution to the original problem. We identify three special cases of this general design technique: (1) Induction or tail-recursion. (2) Nonoverlapping subproblems. (3) Overlapping subproblems with redundant invocations to subproblems, allowing trading space for time. The higher numbered cases subsume the lower numbered ones. The first two cases will not require additional space for the maintenance of solutions for continued reuse. The third class, however, renders the possibility of efficient solutions for many problems that at first glance appear to be time-consuming to solve.

  Chapter 4 is devoted to the study of induction as a technique for the development of algorithms. In other words, the idea of induction in mathematical proofs is carried over to the design of efficient algorithms. In this chapter, several examples are presented to show how to use induction to solve increasingly sophisticated problems.

  Chapter 5 provides a general overview of one of the most important algorithm design techniques, namely divide and conquer. First, we derive divide-and-conquer algorithms for the search problem and sorting by merging. In particular, Algorithm MERGESORT is compared with Algorithm BOTTOMUPSORT presented in Chapter 1 , which is an iterative version of the former. This comparison reveals the most appealing merits of divide-and-conquer algorithms: conciseness, ease of comprehension and implementation, and most importantly the simple inductive proofs for the correctness of divide-and-conquer algorithms. Next, some useful algorithms such as Algorithms quicksort and select for finding the k

  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