tailieunhanh - Lecter Java: Program design - Chapter 11: Recursion

In this chapter we explore en elegant and powerful approach to problem solving recursive problem solving. Recursive problem solving involves breaking a problem into identical, but smaller or simpler problem instances and solving those to obtain a solution to the original problem. Most programming languages, including Java, support the use of recursion to solve problems. | Recursion Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Recursive definitions A definition that defines something in terms of itself is called a recursive definition. The descendants of a person are the person’s children and all of the descendants of the person’s children. A list of numbers is a number or a number followed by a comma and a list of numbers. A recursive algorithm is an algorithm that invokes itself to solve smaller or simpler instances of a problem instances. The factorial of a number n is n times the factorial of n-1. Factorial An imprecise definition A precise definition Ellipsis tells the reader to use intuition to recognize the pattern Recursive methods A recursive method generally has two parts. A termination part that stops the recursion. This is called the base case. The base case should have a simple or trivial solution. One or more recursive calls. This is called the recursive case. The recursive case calls the . | Recursion Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Recursive definitions A definition that defines something in terms of itself is called a recursive definition. The descendants of a person are the person’s children and all of the descendants of the person’s children. A list of numbers is a number or a number followed by a comma and a list of numbers. A recursive algorithm is an algorithm that invokes itself to solve smaller or simpler instances of a problem instances. The factorial of a number n is n times the factorial of n-1. Factorial An imprecise definition A precise definition Ellipsis tells the reader to use intuition to recognize the pattern Recursive methods A recursive method generally has two parts. A termination part that stops the recursion. This is called the base case. The base case should have a simple or trivial solution. One or more recursive calls. This is called the recursive case. The recursive case calls the same method but with simpler or smaller arguments. Method factorial() public static int factorial(n) { if (n == 0) { return 1; } else { return n * factorial(n-1); } } Base case Recursive case deals with a simpler (smaller) version of the task Method factorial() public static int factorial(n) { if (n == 0) { return 1; } else { return n * factorial(n-1); } } public static void main(String[] args) { Scanner stdin = new Scanner(); int n = (); int nfactorial = factorial(n); (n + “! = “ + nfactorial; } Recursive invocation A new activation record is created for every method invocation Including recursive invocations Recursive invocation A new activation record is created for every method invocation Including recursive invocations Recursive invocation A new activation record is created for every method invocation Including recursive invocations Recursive invocation A new activation record is created for every method invocation Including recursive .