More Recursion

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?