官术网_书友最值得收藏!

  • 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:

  1. 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;

  2. 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 );

主站蜘蛛池模板: 肥城市| 修水县| 宜川县| 金华市| 铜陵市| 利辛县| 东辽县| 依兰县| 山东| 佛教| 长丰县| 广州市| 南涧| 温州市| 临漳县| 拉萨市| 利川市| 东阳市| 邯郸市| 桃源县| 连州市| 陵川县| 尚志市| 佛坪县| 永安市| 贵阳市| 宝丰县| 海淀区| 宁明县| 鄂托克前旗| 南汇区| 岳普湖县| 遵义县| 宣城市| 辽中县| 社旗县| 宜兰县| 陆丰市| 若尔盖县| 呈贡县| 澄江县|