Recursive algorithms

As I have already pointed out, recursive algorithms are a different way of thinking about solving a problem. For example, say our problem is to write a program that, given a positive integer n, returns the sum of numbers from zero to n. The known imperative way of writing it is simple:

public int sum_upto(int n){
  int sum=0;
  for(int i=0;i<=n;i++){
    sum+=i;
  }
  return sum;
}

The following would be the functional version of the problem:

public int sum_upto_functional(int n){
  return n==0?0:n+sum_upto_functional(n-1);
}

That's it–just a one-liner! This is probably nothing new to Java programmers, as they do understand recursive functions. However, an imperative programmer would use recursion only when nothing else worked. But this is a different way of thinking. How do we justify that it is equivalent to solving the problem for a smaller input and then composing it with something else? Well, we are certainly first computing the same function for an...