The idea of calling a function to another immediately suggests the possibility of a function calling itself. The mechanism of function call in Java supports this possibility, which is known as recursion. Recursion is a powerful programming technique for general use, and is the key to many important computational applications, ranging from research and combinatorial methods of sorting methods that provide basic support for information processing.
Your first recursive program. HelloWorld for the recursion is to implement the factorial function, defined for positive integers N by the equation
N! = N × (N-1) × (N-2) × ... × 2 × 1
N! is easy to calculate with a for loop, but an even easier in Factorial.java is to use the following recursive function: public static int factorial (int n) {
if (n == 1) return 1;
return N * factorial (N-1);
}
You can convince yourself that it produces the desired result by noting that factorial () returns 1 = 1! when N is 1 and that if he correctly calculates the value
(N-1)! = (N-1) × (N-2) × ... × 2 × 1
Then it calculates the correct value
N! × N = (N-1)! = N × (N-1) × (N-2) × ... × 2 × 1
We can trace this calculation the same way that we draw a sequence of function calls. factorial (5)
factorial (4)
factorial (3)
factorial (2)
factorial (1)
return 1
return 2 * 1 = 2
return 3 * 2 = 6
return 4 * 6 = 24
yield of 5 * 24 = 120
Our implementation exhibits factorial () the two main components that are required for each recursive function.
0 Comments