Preface :
You already have some experience with recursion. A computer file system consists of a root directory that holds files and others directories, calledsubdirectories. Disk backup is recursive because it involves a progress that spawns a like process with the same activities. At each step it performs the simple tasks of copying files and leaves the more complexity task of copying a subdirectory to another (recursive) step, which is just the same process. Eventually the recursive steps lead to a stopping condition in which only files are copied.
Let us look at other process that are recursive. Our goal is to frame the processes as recursive algorithms and then develop ways to implement the algorithms as methods. Some familiar concepts in mathematics provide a good starting point. Consider the problem of evaluating n! (n-factorial), where n is a nonnegative integer. If asked for a definition of n!, most would describe how n! is evaluated ; that is multiply terms from n down to 1.
n! = n * n-1 * n-2 * ... * 2 * 1
This is an iterative view of n-factorial that involves repeated multiplication. When implemented by the method factorial(), a programmer uses a loop to carry out whole operation. Sample code as below :
We can view the factorial in a different way. Consider the evaluation of 4!, assuming we already know that 3! = 6. The problem of evaluating 4! reduces to a single multiplication step using 4 and the prior understanding of 3! :
4! = 4 * 3! = 4 * 6 = 24
This is a new strategy that carries out a calculation which involves a previous result. The strategy can be employed to evaluate 7! as long as we willing to delay each multiplication until we get an intermediate result. The following is an evaluation of 7! assuming that 4! = 24 :
You get the idea. Evaluating n! involves multiplying by a term that is itself a factorial, namely (n-1)!. The process repeats with each step laying out a multiplication operation that has a factorial term with next smaller integer. Ultimately, the process must stop at some n!, which can be evaluated directly. In the example, the process of evaluating 7! stopped at 4! = 24.
In the general case of n!, we choose 0! = 1 as the stopping point. We first setup a series of multiplication statements that evaluate n! for progressively smaller and smaller values of n until we reach the stopping point.
The evaluation of n! is done by revisiting the multiplication steps in reverse order. Each step uses the result from the previous step ; that is , 1! uses the result 0!, 2! uses the result 1! and so forth. The recursive process yields a recursive definition for n!. The form of the definition distinguishes between the stopping step at n=0 and the recursive multiplication step :
Describing a Recursive Algorithm :
The term recursive applies when an algorithm solves a problem by partitioning it into sub-problems that are solved by using the same algorithm. For the factorial algorithm, the partitioning process determines the value of n! by first computing (n-1)!, and so forth. In executing a recursive algorithm, the partitioning process cannot go on indefinitely. So the stopping conditions is required to terminate the recursive process and the factorial has a single stopping condition, n==0.
We use a recursive method to implement a recursive algorithm. The design of a recursive method consists of the following elements :
Implementing Recursive Methods :
The design of a recursive method must carefully distinguish between the stopping condition and the recursive step. A programmer implements the distinction with an if-else statement. The if-portion handles the stopping condition, and the else portion handles the recursive step. In the case of the factorial() method, the if-portion evaluate the single stopping condition n==0 and return a result 1. The else-portion first calls factorial() with argument n-1 and then returns the result of the expression n*(n-1)!.
How Recursion Works :
A recursive algorithm is an alternative form of an iterative process. What makes recursive algorithm difficult to understand is the fact that the method implementation use only a simple if-else statement that hides the underlying repetitive process. In this section, we illustrate the process for factorial(3) by tracing the recursive steps to the stopping condition and then retracing the steps to the ultimate return value.
Executing the method recursiveFact() sets in motion a whole series of method calls and calculations. Think of recursiveRact(n) as a machine called n-Fact that computes n! by carrying out the multiplication n*(n-1)!. In order for the machine to operate, it must be networked with a series of other n-Fact machines that pass information back and forth. The 0-Fact machine is stopping point. It can work independently and produce the result 1 without assistance from another machine. Below figure illustrate the networking and iteration of machines, starting with 3-Fact, which computes 3! :
Once 0-Fact is activated, it immediately computes 0!=1 and returns the value to the 1-Fact machine which is then capable of completing the operation 1* 0! = 1. So the ultimate result 3! can be reached.
Multibase Representations :
In most programming languages, computers display numbers in decimal (base-10) format by default. It is sometimes useful to display numbers in others bases. For instance, the number n=95 has the following representations in bases 2, 5 and 8 :
An integer n > 0 can be represented in different bases by using repeated division. The process generates the digits for the number from right to left by using the "%" and "/" operators. The remainder is the next digit and the quotient identifies the remaining digits. For instance, n = 95 is 137 base 8. See how the repeated division process identifies the digits for the base-8 number in the order "7", "3" and "1". In the representation, the digits appear in the opposite order of their discovery :
The recursive method baseString() provides a representation of a non-negative number in any base from 2 to 16. The method takes a decimal number n and a base b, where 2<= b <=16, and returns a string that is the corresponding representation. The method uses repeated division. If n/b is not 0, the recursive step first looks at the quotient (remaining digits) by calling baseString() with n/b as the argument. This recursive call returns a string with the representation of n/b. The step then returns a new string that combines the digits from n/b and the digit n%b. When the quotient is 0, we reach the stopping condition and just return the empty string "". The below figure illustrate the series of recursive steps used by baseString() to output 95 base 10 in base 8 :
The baseString() implementation is show below :
You already have some experience with recursion. A computer file system consists of a root directory that holds files and others directories, calledsubdirectories. Disk backup is recursive because it involves a progress that spawns a like process with the same activities. At each step it performs the simple tasks of copying files and leaves the more complexity task of copying a subdirectory to another (recursive) step, which is just the same process. Eventually the recursive steps lead to a stopping condition in which only files are copied.
Let us look at other process that are recursive. Our goal is to frame the processes as recursive algorithms and then develop ways to implement the algorithms as methods. Some familiar concepts in mathematics provide a good starting point. Consider the problem of evaluating n! (n-factorial), where n is a nonnegative integer. If asked for a definition of n!, most would describe how n! is evaluated ; that is multiply terms from n down to 1.
n! = n * n-1 * n-2 * ... * 2 * 1
This is an iterative view of n-factorial that involves repeated multiplication. When implemented by the method factorial(), a programmer uses a loop to carry out whole operation. Sample code as below :
We can view the factorial in a different way. Consider the evaluation of 4!, assuming we already know that 3! = 6. The problem of evaluating 4! reduces to a single multiplication step using 4 and the prior understanding of 3! :
4! = 4 * 3! = 4 * 6 = 24
This is a new strategy that carries out a calculation which involves a previous result. The strategy can be employed to evaluate 7! as long as we willing to delay each multiplication until we get an intermediate result. The following is an evaluation of 7! assuming that 4! = 24 :
You get the idea. Evaluating n! involves multiplying by a term that is itself a factorial, namely (n-1)!. The process repeats with each step laying out a multiplication operation that has a factorial term with next smaller integer. Ultimately, the process must stop at some n!, which can be evaluated directly. In the example, the process of evaluating 7! stopped at 4! = 24.
In the general case of n!, we choose 0! = 1 as the stopping point. We first setup a series of multiplication statements that evaluate n! for progressively smaller and smaller values of n until we reach the stopping point.
The evaluation of n! is done by revisiting the multiplication steps in reverse order. Each step uses the result from the previous step ; that is , 1! uses the result 0!, 2! uses the result 1! and so forth. The recursive process yields a recursive definition for n!. The form of the definition distinguishes between the stopping step at n=0 and the recursive multiplication step :
Describing a Recursive Algorithm :
The term recursive applies when an algorithm solves a problem by partitioning it into sub-problems that are solved by using the same algorithm. For the factorial algorithm, the partitioning process determines the value of n! by first computing (n-1)!, and so forth. In executing a recursive algorithm, the partitioning process cannot go on indefinitely. So the stopping conditions is required to terminate the recursive process and the factorial has a single stopping condition, n==0.
We use a recursive method to implement a recursive algorithm. The design of a recursive method consists of the following elements :
Implementing Recursive Methods :
The design of a recursive method must carefully distinguish between the stopping condition and the recursive step. A programmer implements the distinction with an if-else statement. The if-portion handles the stopping condition, and the else portion handles the recursive step. In the case of the factorial() method, the if-portion evaluate the single stopping condition n==0 and return a result 1. The else-portion first calls factorial() with argument n-1 and then returns the result of the expression n*(n-1)!.
How Recursion Works :
A recursive algorithm is an alternative form of an iterative process. What makes recursive algorithm difficult to understand is the fact that the method implementation use only a simple if-else statement that hides the underlying repetitive process. In this section, we illustrate the process for factorial(3) by tracing the recursive steps to the stopping condition and then retracing the steps to the ultimate return value.
Executing the method recursiveFact() sets in motion a whole series of method calls and calculations. Think of recursiveRact(n) as a machine called n-Fact that computes n! by carrying out the multiplication n*(n-1)!. In order for the machine to operate, it must be networked with a series of other n-Fact machines that pass information back and forth. The 0-Fact machine is stopping point. It can work independently and produce the result 1 without assistance from another machine. Below figure illustrate the networking and iteration of machines, starting with 3-Fact, which computes 3! :
Once 0-Fact is activated, it immediately computes 0!=1 and returns the value to the 1-Fact machine which is then capable of completing the operation 1* 0! = 1. So the ultimate result 3! can be reached.
Multibase Representations :
In most programming languages, computers display numbers in decimal (base-10) format by default. It is sometimes useful to display numbers in others bases. For instance, the number n=95 has the following representations in bases 2, 5 and 8 :
An integer n > 0 can be represented in different bases by using repeated division. The process generates the digits for the number from right to left by using the "%" and "/" operators. The remainder is the next digit and the quotient identifies the remaining digits. For instance, n = 95 is 137 base 8. See how the repeated division process identifies the digits for the base-8 number in the order "7", "3" and "1". In the representation, the digits appear in the opposite order of their discovery :
The recursive method baseString() provides a representation of a non-negative number in any base from 2 to 16. The method takes a decimal number n and a base b, where 2<= b <=16, and returns a string that is the corresponding representation. The method uses repeated division. If n/b is not 0, the recursive step first looks at the quotient (remaining digits) by calling baseString() with n/b as the argument. This recursive call returns a string with the representation of n/b. The step then returns a new string that combines the digits from n/b and the digit n%b. When the quotient is 0, we reach the stopping condition and just return the empty string "". The below figure illustrate the series of recursive steps used by baseString() to output 95 base 10 in base 8 :
The baseString() implementation is show below :
This message was edited 11 times. Last update was at 16/09/2010 18:20:15
沒有留言:
張貼留言