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
10 Key excerpts on "Recursion Programming"
eBook - ePub- 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)
eBook - ePubProgramming Fundamentals Using JAVA
A Game Application Approach
- William McAllister, S. Jane Fritz(Authors)
- 2021(Publication Date)
- Mercury Learning and Information(Publisher)
Figure 9.1 illustrates both of these forms of recursion.Figure 9.1The two forms of recursive methods.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 * 1This non-recursive definition of 10! can be generalized to a non-recursive definition of n! for any positive value of n.DefinitionAlternately, the definition of 10! can be more succinctly stated recursively asThe non-recursive definition of n! for values of n ≥ 0n! ≡ n * (n - 1) * (n - 2) * (n – 3) * (n – 4)* ....* 3 * 2 * 1 and 0! ≡ 110! ≡ 10 * (10 - 1)! and 0! ≡ 1This recursive definition can be generalized to a recursive definition of n! for any positive value of n.DefinitionThe equivalence of the recursive and non-recursive definitions can be easily understood by examining the non-recursive definition of 10! and 9!The recursive definition of n!n! ≡ n * (n - 1)! and 0! ≡ 1The 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!.
eBook - ePubMastering 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:
eBook - ePubProgramming 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 * 1This non-recursive definition of 10! can be generalized to a non-recursive definition of n! for any positive value of n.Alternately, the definition of 10! can be more succinctly stated recursively asDefinitionThe non-recursive definition of n! for values of n ≥ 0n! ≡ n * (n - 1) * (n - 2) * (n – 3) * (n – 4)* ....* 3 * 2 * 1 and 0! ≡ 110! ≡ 10 * (10 - 1)! and 0! ≡ 1This recursive definition can be generalized to a recursive definition of n! for any positive value of n.The equivalence of the recursive and non-recursive definitions can be easily understood by examining the non-recursive definition of 10! and 9!DefinitionThe recursive definition of n!n! ≡ n * (n - 1)! and 0! ≡ 1The 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!.
eBook - ePubEssential Algorithms
A Practical Approach to Computer Algorithms Using Python and C#
- Rod Stephens(Author)
- 2019(Publication Date)
- Wiley(Publisher)
CHAPTER 9 RecursionRecursion 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.
eBook - ePubProgramming Interviews Exposed
Coding Your Way Through the Interview
- John Mongan, Noah Suojanen Kindler, Eric Giguère(Authors)
- 2018(Publication Date)
- Wrox(Publisher)
8 RecursionRecursion is a deceptively simple concept: any function that calls itself is recursive. Despite this apparent simplicity, understanding and applying recursion can be surprisingly complex. One of the major barriers to understanding recursion is that general descriptions tend to become highly theoretical, abstract, and mathematical. Although there is certainly value in that approach, this chapter instead follows a more pragmatic course, focusing on example, application, and comparison of recursive and iterative (nonrecursive) algorithms.UNDERSTANDING RECURSION
Recursion is useful for tasks that can be defined in terms of similar subtasks. For example, sort, search, and traversal problems often have simple recursive solutions. A recursive function performs a task in part by calling itself to perform the subtasks. At some point, the function encounters a subtask that it can perform without calling itself. This case, in which the function does not recurse, is called the base case; the former, in which the function calls itself to perform a subtask, is referred to as the recursive case.NOTE
Recursive algorithms have two cases: recursive cases and base cases.These concepts can be illustrated with a simple and commonly used example: the factorial operator. n! (pronounced “n factorial”) is the product of all integers between n and 1. For example, 4! = 4 · 3 · 2 · 1 = 24. n! can be more formally defined as follows:n! = n (n – 1)!0! = 1! = 1This definition leads easily to a recursive implementation of factorial. The task is to determine the value of n!, and the subtask is to determine the value of (n! – 1)!. In the recursive case, when n is greater than 1, the function calls itself to determine the value of (n – 1)! and multiplies that by n. In the base case, when n
eBook - ePubAlgorithms: 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 RecursionThis 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
eBook - ePubData Structures using C
A Practical Approach for Beginners
- Amol M. Jagtap, Ajit S. Mali(Authors)
- 2021(Publication Date)
- Chapman and Hall/CRC(Publisher)
1Fundamental Principles of Algorithm and RecursionDOI: 10.1201/9781003105800-11.1 Algorithm, Its Pseudo-Code Representation and FlowChart
1.1.1 Algorithm Definition
An algorithm is a step-by-step procedure for solving a problem. A sequential solution to any program that is scripted in any natural language is called as an algorithm. The algorithm is the first step of the solving process. After the problem analysis, the developer writes the algorithm for this problem. It is largely used for data processing, computing and other related computer and mathematical operations.The algorithm must satisfy the following five conditions:- Input: Zero, one or more quantities are externally provided.
- Output: The algorithm produces at least one output as a result.
- Definiteness: Each statement must be clear, specific, and unambiguous.
- Finite: The algorithm should conclude after a limited number of steps.
- Effectiveness: Every statement must be very fundamental so that it can be carried out by any individual using only paper and pencil.
1.1.2 Pseudo-Code Representation
The word “pseudo” means “fake,” so “pseudo-code” means “fake code”. Pseudo-code is an informal language used by programmers to develop algorithms. Pseudo-code describes how you would implement an algorithm without getting into syntactical details. It uses the structural conventions of a formal programming language but is proposed for human reading rather than machine reading. It is used to create an overview or outline of a program. System designers write pseudo-code to make sure the programmer understands a software project’s requirements and aligns the code accordingly. The pseudo-code contains no variable declaration.
- 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 Matchingmatch versus switch5.6 Bad Input, Exceptions, and the try/catch Expression5.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 ProjectsGaining 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 RecursionRecursion 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
eBook - ePub- Sachi Nandan Mohanty, Pabitra Kumar Tripathy, Suneeta Satpathy(Authors)
- 2021(Publication Date)
- Chapman and Hall/CRC(Publisher)
2Concepts of Algorithms and Recurrences
DOI: 10.1201/9781003093886-22.1 Algorithm
An algorithm can be defined in different ways as given below:- It is a set of rules for carrying out calculations either by hand or by a machine.
- It is a finite number of step-by-step procedures to achieve a required result.
- It is a sequence of computational steps that transform the input into the output.
- It is a sequence of operations performed on the data, which has to be organized in data structures.
- It is an abstraction of a program to be executed on a physical machine (mode of computation).
- Design of algorithms
- Algorithm validation
- Analysis of algorithms
- Algorithm testing.
2.2 Design of Algorithms
Several methods are used to design an algorithm, but out of those, some most commonly used algorithms are- Divide-and-conquer
- Incremental approach
- Dynamic programming
- Brute force approach
- Decrease and conquer
- Backtracking
- Greedy approach.
- Algorithm Validation
This step checks the algorithm result for all sets of legal input. It is a highly essential step to check for the validation of an algorithm after writing it. In this step, the algorithm is not converted into a program. After showing the validity of the methods, a program can be written by using any one of the languages. This phase is also known as program proving or program verification.
- Analysis of Algorithms
In most cases, for a specific problem, several solutions may be proposed in terms of algorithms, and it’s too difficult to choose a proper algorithm that will result in the best output. In this step, analysis of the number of algorithms has to be performed to get the best algorithm, which means there will be a comparison among the algorithms.
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.
