Structures Can Be Stacked or Connected to One Another at Their ____.

Recursion

By and large speaking, recursion is the concept of well-defined cocky-reference. It is the decision of a succession of elements by operating on one or more preceding elements according to a rule or a formula involving a finite number of steps.

In information science, recursion is a programming technique using function or algorithm that calls itself one or more times until a specified condition is met at which time the rest of each repetition is processed from the last one called to the beginning.

For example, let's wait at a recursive definition of a person's ancestors:

• 1'due south parents are one's ancestors
• The parents of whatever ancestor are also ancestors of the person nether consideration

We can write pseudocode to decide whether somebody is someone's ancestor.

Part isAncestor(Person x, Person y):
IF x is y's parent, Then:
return true
ELSE
return isAncestor(10, y'due south mom) OR isAncestor(10, y's dad)
}

This is a recursive office that calls itself. Observe that at that place'due south a case when the part does not phone call itself recursively, otherwise, the function volition keep calling itself and will never stop to return a value. Thus, a recursive function normally has a certain structure: (i) a base case, which does not call the role itself; and (ii) a recursive footstep, which calls the role itself and moves closer to the base case. Even with the right structure, we yet need to exist careful to infiniteness. You may accept noticed that the to a higher place function isAncestor still has some problem. What if x is non an antecedent of y? Then the program will keep request about if x is y's parents' ancestor, then on. It will never reach the base case, and the list of parents will go much further back. The program will never end. The problem here is the base of operations case here is not complete. We should add together a new base case:

Role isAncestor(Person 10, Person y):
IF 10 is y's parent, THEN:
return true
ELSE IF ten was non born earlier y was born, THEN:
return fake
ELSE
return isAncestor(x, y's mom) OR isAncestor(x, y's dad)
}

Of import: Every recursion must have at to the lowest degree ane base of operations case, at which the recursion does non recur (i.e., does not refer to itself).

More than examples of recursion:

• Russian Matryoshka dolls. Each doll is made of solid woods or is hollow and contains another Matryoshka doll inside information technology.
• Modernistic OS defines file organisation directories in a recursive way. A file organisation consists of a top-level directory, and the contents of this directory consists of files and other directories.
• Much of the syntax in modernistic programming languages is defined in a recursive way. For example, an argument listing consists of either (1) an argument or (two) an argument list followed past a comma and an argument.

Practice: give a recursive definition of the post-obit data structures:

• A linked list
• Number of nodes in a linked list

Defining Issues in Ways That Facilitate Recursion

To design a recursive algorithm for a given problem, it is useful to remember of the different ways we tin can subdivide this problem to define problems that have the same general structure equally the original problem. This process sometimes means nosotros need to redefine the original problem to facilitate similar-looking subproblems.

Some observations: (1) Avoid if possible recursive functions that make multiple overlapping calls to themselves, which leads to an exponential complication; and (two) repetition in code can be achieved through recursion.

In the following examples, you should always ask yourself what are the base of operations example and the recursive step, notation the naturalness of the implementation, understand how the loop replacement characteristic of recursion is involved, and possibly call back virtually what is the running time and infinite usage.

Example ane: Factorial Calculation

We know that the factorial of n (n >= 0) is calculated past n! = n * (n-1) * (n-2) * ... * two * 1.  Note that the production of (n-1) * (due north-2) * ... * 2 * i is exactly (n-1)!. Thus we can write the expression equally n! = n * (n-1)!, which is the recursive expression of the factorial adding.

What is the base of operations case? What is the recursive pace?

public class RecursiveFactorial {
public static void chief (String[] args) {
for (int i = one; i < x; i++)
System.out.println(i + "\t" + factorial(i));
}
static int factorial (int n) {
if (due north < two) return 1;                     // base example
else return n * factorial(n-1);    // recursive case
}
}

The above recursion is called a linear recursion since it makes i recursive phone call at a fourth dimension. The loop equivalent:

public static int factorial(int n) {
int outcome = 1;
for (int i = two; i <= n; i++)
result *= i;
return result;
}

Recursion and Stacks

Allow'due south take a close wait at the mechanism with which a recursive program is actually implemented by the compiler. In the previous example, we accept seen how a recursion executes its forward and backing-out phases. The order in which the recursive process backs out is the contrary of the club in which information technology goes forward. Thus some action may be performed that involves recalling something that has been stored in the forward procedure. The compiler uses a stack to implement recursion.

• In the forwarding phase, the values of local variables and parameters, and the render accost are pushed on the stack for every level of the recursion
• In the backing-out phase, the stacked address is popped and used to return to executing the remainder of the code in the calling level, and the stacked local variables and parameters are popped and used to restore the country of that phone call

Exercise

• Exponentiation. Summate xⁿ using both iteration and recursion. (Assume x > 0 and n >= 0)

Example 2: Reversing an Array

Permit us consider the trouble of reversing the n elements of an array, A, so that the commencement element becomes the final, the 2nd chemical element becomes the 2nd to the concluding, and so on. Nosotros tin can solve this problem using the linear recursion, by observing that the reversal of an array can be achieved by swapping the first and terminal elements and then recursively reversing the remaining elements in the array.

Algorithm ReverseArray(A, i, j):
Input: An array A and nonnegative integer indices i and j
Output: The reversal of the elements in A starting at index i and ending at j
if i < j and then
Swap A[i] and A[j]
ReverseArray(A, i+1, j-1)
return

Exercises

• Summing the elements of an assortment recursively
• Finding the maximum element in an assortment A of n elements using recursion

Example three: Towers of Hanoi

This is a standard problem where the recursive implementation is lilliputian but the non-recursive implementation is nearly incommunicable.

In the Towers of Hanoi puzzle, we are given a platform with iii pegs, a, b, and c, sticking out of it. On peg a is a stack of n disks, each larger than the side by side, and then that the smallest is on the summit and the largest is on the lesser. The puzzle is to move all the disks from peg a to c, moving one disk at a fourth dimension, and then that we never place a larger disk on top of a smaller one. The following figures give an example of the starting position and the ending position of the disks with due north = 4. Let'due south look at an example of moving iv disks.

a                       b                 c                                                a                 b                   c
(source)              (spare)         (dest)                                        (source)       (spare)          (dest)

Think about what is the base case? What is the recursive footstep?

At the acme level, we desire to move four disks from peg a to c, with a spare peg b. We can intermission the problem of moving 4 disks into three steps:

1. Move disk 3 and smaller from peg a to b, using c as a spare peg. This can be done by recursively calling the same procedure only with three disks instead. After this procedure, we will have iii smaller disks on peg b.
2. Move disk 4 from peg a to peg c. After this process, we will have 3 smaller disks on peg b, deejay 4 on peg c, and peg a empty.
3. Move deejay iii and smaller from peg b to c, using a as spare peg. Once again, this can be washed by recursively calling the aforementioned procedure on 3 disks with different source and destination. After this procedure, nosotros will accept all the disks on peg c without breaking the rules.

The pseudocode looks similar the following. We call this function to move 4 disks by MoveDisk(iv, a, c, b).

Algorithm MoveDisk(deejay, source, dest, spare) {
if (deejay = = 1) so
move disk from source to dest
else
MoveDisk(disk-1, source, spare, dest)      // step 1 above
move disk from source to dest                    // footstep 2 above
MoveDisk(disk-1, spare, dest, source)       // step iii higher up
}

Let'south trace our solution. To visualize the recursive calling process, we generate a call tree. This is a call tree for moving three disks from peg a to c.

Notice that, each MoveDisk call will branch into two functions calls unless information technology's the base instance. If we want to movement northward disks, how many movements practice nosotros need with this recursive office?

Presume M(i) represents the number of movement for the disks, let's calculate how long does it accept to move due north disks.

• Grand(1) = 1
• Grand(2) = 2M(1) + 1 = 3
• M(iii) = 2M(2) + ane = 7
• Thousand(4) = 2M(three) + one = 15
• ...
• We can gauge Chiliad(n) = 2 ^north - 1

This can be verified by plugging it into our function.

• G(1) = 2¹ - i
• K(n) = 2M(n-1) + 1 = two[2M(northward-two) + 1] + ane = ... = 2 ^k M(n-k) + 2 ^{one thousand-1} + 2 ^k-2 + ... + 2 + 1
• 1000(northward) = 2 ⁿ - ane when k = due north-i (stopping at the base of operations instance)

A 64-disk version of the puzzle lies in a Hanoi monastery, where monks continuously toward solving the puzzle. When they complete the puzzle, the world will come to an end. Now, you know the answer. How long will the globe last? roughly 585.442 billion years. The universe is currently about 13.vii billion years old.

Example 4: Fibonacci Sequence

Fibonacci sequence is the sequence of numbers 1, 1, two, 3, 5, 8, 13, 21, 34, 55, .... The first ii numbers of the sequence are both i, while each succeeding number is the sum of the two numbers before information technology. Nosotros can define a part F(n) that calculates the nth Fibonacci number.

First, the base cases are: F(0) = one and F(i) = 1.

Now, the recursive case: F(n) = F(north-ane) + F(n-2).

Write the recursive function and the telephone call tree for F(5).

Algorithm Fib(north) {
if (n < 2) return 1
else return Fib(n-i) + Fib(n-2)
}

The in a higher place recursion is called binary recursion since it makes two recursive calls instead of one. How many number of calls are needed to compute the grandth Fibonacci number? Allow n_thou announce the number of calls performed in the execution.

• n₀ = 1
• n_one = 1
• northward₂ = n₁ + due north₀ + 1  = iii > 2ⁱ
• north_iii = northward₂ + n₁   + i = 5 > ii²
• n_four = n_iii + northward₂ + 1 = 9 > 2³
• due north_five = n₄ + north₃ + 1 = 15 > 2³
• ...
• northward_thou   > 2 ^g/2

This means that the Fibonacci recursion makes a number of calls that are exponential in k. In other words, using binary recursion to compute Fibonacci numbers is very inefficient.  Compare this problem with binary search, which is very efficient in searching items, why is this binary recursion inefficient? The principal trouble with the arroyo higher up, is that in that location are multiple overlapping recursive calls.

We can compute F(northward) much more efficiently using linear recursion. One fashion to accomplish this conversion is to ascertain a recursive part that computes a pair of sequent Fibonacci numbers F(n) and F(north-1) using the convention F(-i) = 0.

Algorithm LinearFib(northward) {
Input: A nonnegative integer n
Output: Pair of Fibonacci numbers (F _n , F _n-1)
if (n <= i) then
render (due north, 0)
else
(i, j) <-- LinearFib(north-1)
return (i + j, i)
}

Since each recursive telephone call to LinearFib decreases the argument n past i, the original phone call results in a series of n-1 additional calls. This operation is significantly faster than the exponential time needed by the binary recursion. Therefore, when using binary recursion, nosotros should first effort to fully segmentation the problem in two or, nosotros should be sure that overlapping recursive calls are really necessary. Usually, we can eliminate overlapping recursive calls by using more memory to keep track of previous values. In fact, this arroyo is a central part of a technique called dynamic programming. Allow'southward utilize iteration to generate the Fibonacci numbers. What's the complexity of this algorithm?

public static int IterationFib(int n) {
if (n < ii) return n;
int f0 = 0, fane = one, f2 = 1;
for (int i = 2; i < n; i++) {
f0 = fi;
f1 = f2;
ftwo = f0 + fi;
}
render f2;
}

Example 5: Binary Search

What'due south the base instance? What's the recursive case?

public grade TestBinarySearch {
TestBinarySearch() {
int[] arr = {22, 33, 44, 55, 66, 77, 88, 99};
System.out.println("search(" + 55 + "): " + BinarySearch(arr, 0, arr.length-1, 55));
System.out.println("search(" + 50 + "): " + BinarySearch(arr, 0, arr.length-i, l));
}

    public static void main(Cord[] args) {
new TestBinarySearch();
}

    int BinarySearch(int[] arr, int beginning, int end, int x) {
int mid = (kickoff + end) / 2;
if (arr[mid] = = x) render mid;
if (outset > finish) return -1;
if (arr[mid] < x) render BinarySearch(arr, mid+one, end, x);
else return BinarySearch(arr, start, mid-1, ten);
}
}

Exercise

• Summing the elements in an array using the binary recursion

Drawbacks of Recursion

Recursion consumes stack space. Every recursive method telephone call produces a new instance of the method, one with a new set of local variables. The total stack space used depends upon the level of nesting of the recursion procedure, and the number of local variables and parameters.

Recursion may perform redundant computations. Consider the recursive computation of the Fibonacci sequence.

In sum, ane has to weigh the simplicity of the lawmaking delivered by recursion against its drawbacks as described above. When a relatively simple iterative solution is possible, it is definitely a better culling.

Tail Recursion

We tin convert a recursive algorithm into a non-recursive algorithm and there are some instances when we tin can do this conversion more than easily and efficiently. Specifically, we can easily convert algorithms that utilise tail recursion. An algorithm uses tail recursion if information technology uses linear recursion and the algorithm makes a recursive call as its very last operation. The recursive phone call must exist absolutely the terminal affair the method does. For instance, the examples 1, two and v are all tail recursion, and can be easily implemented using iteration.

Exercises

Either write the pseudo-code or the Java code for the following issues. Draw the recursion trace of a elementary case. What is the running time and space requirement?.

1. Recursively searching a linked list
2. Forward printing a linked list
3. Reverse printing a linked list

mchughcataing.blogspot.com

Source: https://www.cpp.edu/~ftang/courses/CS240/lectures/recursion.htm