- The Java Workshop
- David Cuartielles Andreas G?ransson Eric Foster Johnson
- 481字
- 2021-06-11 13:05:22
Recursion
Programming languages allow the usage of certain mechanisms to simplify solving a problem. Recursion is one of those mechanisms. It is the ability of a method to call itself. When properly designed, a recursive method can simplify the way a solution to a certain problem is expressed using code.
Classic examples in recursion include the computation of the factorial of a number or the sorting of an array of numbers. For the sake of simplicity, we are going to look at the first case: finding the factorial of a number.
class Example11 {
public static long fact ( int n ) {
if ( n == 1 ) return 1;
return n * fact ( n – 1 );
}
public static void main(String[] args) {
int input = Integer.parseInt(args[0]);
long factorial = fact ( input );
System.out.println(factorial);
}
}
To run this code, you will need to go to the terminal and call the example from there with java Example11 m, where m is the integer whose factorial will be calculated. Depending on where you created the project on your computer, it could look like this (note that we have shortened the path to the example to keep it clean):
usr@localhost:~/IdeaProjects/chapter03/[...]production/Example11$ java Example11 5
120
Or, it could look like this:
usr@localhost:~/IdeaProjects/chapter03/[...]production/Example11$ java Example11 3
6
The result of the call is the factorial: 120 is the factorial of 5, and 6 is the factorial of 3.
While it might not seem so intuitive at first sight, the fact method calls itself in the return line. Let's take a closer look at this:
public static long fact ( int n ) {
if ( n == 1 ) return 1;
return n * fact ( n – 1 );
}
There are a couple of conditions that you need to meet when designing a functional recursive method. Otherwise, the recursive method will not converge to anything:
- There needs to be a base condition. This means you need something that will stop the recursion from happening. In the case of the fact method, the base condition is n being equal to 1:
if ( n == 1 ) return 1;
- There needs to be a way to computationally reach the base condition after a certain number of steps. In our case, every time we call fact, we do it with a parameter that is one unit smaller than the parameter of the current call to the method:
return n * fact ( n – 1 );
- Go Web編程
- Visual FoxPro程序設(shè)計教程(第3版)
- AngularJS Web Application Development Blueprints
- Programming ArcGIS 10.1 with Python Cookbook
- Learning SciPy for Numerical and Scientific Computing(Second Edition)
- Java EE 8 Application Development
- Java高并發(fā)核心編程(卷1):NIO、Netty、Redis、ZooKeeper
- Java語言程序設(shè)計教程
- Learning Docker Networking
- Unity&VR游戲美術(shù)設(shè)計實戰(zhàn)
- 計算機應(yīng)用基礎(chǔ)(第二版)
- C語言程序設(shè)計
- Java Web程序開發(fā)參考手冊
- Ajax與jQuery程序設(shè)計
- Modern R Programming Cookbook