Objectives
- Explain what recursion is
- Use a recursive method
- Write a recursive method given a recursive formula or algorithm
Recursion
Recursion is when a method calls itself, either directly or indirectly. This is an easy concept for some, but not for most. This topic usually emerges naturally when data structures are being discussed. The text contains a number of examples of recursion. The examples that use data structures beyond arrays are beyond the scope of this course.
Example: Reverse a String
Algorithm: Given a string s If the length of s is 0 or 1, return s Otherwise return the last character of s plus the rest of the string reversed public class RecurseBed { public static void main(String[] args) { System.out.println(reverse("This is a test string!")); } private static String reverse(String s) { int len = s.length(); if (len < 2) return s; else return s.charAt(len-1) + reverse(s.substring(0, len-1)); } } // Displays: // !gnirts tset a si sihT
Example: Factorial
Algorithm: Given a non-negative integer n If n is 0, then return 1 Otherwise return n * factorial of n-1 private static long fact(long n) { if (n == 0) return 1; else return n * fact(n-1); }
Example: Fibonacci
Algorithm: Given a non-negative integer n If n is 0 or 1, then return n Otherwise return Fibonacci of n-1 + Fibonacci of n-2 private static long fib(long n) { if (n < 2) return n; else return fib(n-1) + fib(n-2); }
Example: Greatest common divisor (GCD)
Algorithm: Given integers m and n, both greater than 0 where m is at least as large as n... If n divides m with no remainder, then return n Otherwise return the GCD of n and the remainder of m / n private static int gcd(int m, int n) { int rem = m % n; if (rem == 0) return n; else return gcd(n, rem); }