## 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 input that is...