Definition of Tail Recursion: A method is "tail recursive" if NO work is done after the recursive call. Which of these methods are tail recursive? int sum(int n): _________________________________________ long factorial(long n): _________________________________ long power(long x, long n): _____________________________ boolean search(int[] array, int size, int value): ________ int fib(int n): __________________________________________ Tail recursive methods can be directly translated to a loop by the compiler! We can rewrite the sum method using tail recursion, but we need an extra parameter to keep track of the sum as we go along: int sum(int n, int sumSoFar) { } We can trace the method calls for sum(4,0): Iteration vs. Recursion: Anything that can be done iteratively can be done recursively and vice-versa! Sometimes recursive methods are much simpler than iterative methods.... but recursion involves the overhead of many method calls. How does the following program get its input? What's wrong with it? What happens when it is executed? Try it and see!!: public class Crash { public static int sum(int n) { if (n == 0) return 0; else return n + sum(n); } public static void main(String[] args) { if (args.length == 1) { try { int n = Integer.parseInt(args[0]); System.out.println(sum(n)); } catch(NumberFormatException e) { System.out.println("Please enter an integer!"); } } } } What happens if a legitimate method makes too many recursive calls?