Recursion

• Describe the concept of recursion
• Use recursion as a programming tool JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch

• A recursive algorithm will have one subtask that is a small version of the entire algorithm's task
• A recursive algorithm contains an invocation of itself
• Must be defined correctly else algorithm could call itself forever or not at all JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch

• Next handle larger cases; phrase solution in terms of a smaller version of the same problem is to output 3 then output
• countDown(3) the result of countDown(2) View demonstration, listing 11.1 class RecursionCountdown JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch

• See code for count down JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch

• Must have a branching statement that leads to different cases
• One or more of the branches should have a recursive call of the method
  • Recursive call must us "smaller" version of the original argument
• One or more branches must include no recursive call
  • This is the base or stopping case JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch

• Nothing stops the method from repeatedly invoking itself
  • Program will eventually crash when computer exhausts its resources (stack overflow) JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch

• Recursive method
  • Uses more storage space than iterative version
  • Due to overhead during runtime
  • Also runs slower
• However in some programming tasks, recursion is a better choice, a more elegant solution JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch

• For some problems, it’s useful to have a method call itself.
• A method that does so is known as a recursive method.
• A recursive method can call itself either directly or indirectly through another method. JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch

• Recursion is the process of defining something in terms of itself. As it relates to java programming, recursion is the attribute that allows a method to call itself. A method that calls itself is said to be recursive. JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch

• Tail recursion is defined as occurring when the recursive call is at the end of the recursive instruction. It is useful to notice when ones algorithm uses tail recursion because in such a case, the algorithm can usually be rewritten to use iteration instead. (ex: count Down) JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch

• Figure 18.2(a) shows how the succession of recursive calls proceeds until 1! (the base case) is evaluated to be 1, which terminates the recursion.
• Figure 18.2(b) shows the values returned from each recursive call to its caller until the final value is calculated and returned.
• Figure 18.3 uses recursion to calculate and print the factorials of the integers from 0– 21. JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch

• The recursive method factorial (lines 7–13) first tests to determine whether a terminating condition (line 9) is true.
• If number is less than or equal to 1 (the base case), factorial returns 1, no further recursion is necessary and the method returns.
• If number is greater than 1, line 12 expresses the problem as the product of number and a recursive call to factorial evaluating the factorial of number - 1, which is a slightly smaller problem
• than the original calculation, factorial(number ). JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch

• See code for factorial JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch

• See code for Fibonacci JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch

JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch

© Copyright 1992-2012 by Pearson

Write a recursive method power(base, exponent) that, when called, returns base

exponent

For example, power(3,4) = 3 * 3 * 3 * 3.

Assume that exponent is an integer greater than or equal to 1.

[ Hint: The recursion step should use the relationship

exponent = base · base

exponent – 1

base and the terminating condition occurs when exponent is equal to 1, because

1 = base

base Incorporate this method into a program that enables the user to enter the base and exponent.]

JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch

JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch

run:

Enter base: 3 Enter exponent: 4 Value is 81 BUILD SUCCESSFUL (total time: 10 seconds)

JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch

• See code JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch

• Method with self invocation
  • Invocation considered a recursive call
• Recursive calls
  • Legal in Java
  • Can make some method definitions clearer
• Algorithm with one subtask that is smaller version of entire task
  • Algorithm is a recursive method JAVA: An Introduction to Problem Solving & Programming, 6 th Ed. By Walter Savitch