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 smaller by one and then just adding n to it. There is one more thing to note here: in the imperative version, we are updating the variable called sum for each value of the loop variable i. However, in the functional version, we are not updating any variable. What do we achieve by that? When a variable is updated multiple times in a program, it is hard to understand or debug it because you need to keep track of the latest value. When this does not happen, it is far easier to understand what is happening. In fact, it makes it simpler in such a way that we can even prove the correctness of the program completely formally, which is rather hard to do for imperative programs where variables change values.

Let's check out another example. This one is about choosing r objects from n objects, where the order does not matter. Let's have a set A of a finite amount of objects. Let the number of objects in this set be n. How many subsets B of this set A have exactly r elements? Of course, the maximum number of elements any subset of A can have is n; hence r ≤ n. We will call this function choose. So, we write this as choose(n,r). Now, the only subset that has an equal number of elements as A is A itself. So, choose(n,n) equals 1.

How do we break this problem into subproblems of a similar nature but with smaller input? To find out how many subsets B have r elements, we first think of the set A as a combination of a subset C with n-1 elements and one particular element a. So, we can say A = C ⋃ {a}. Now, we consider two disjoint cases: the element a is a member of the subset B and when it is not a member of the subset B. When a is not a member of the subset B, B is also a subset of C. The number of such subsets B with exactly r elements is choose(n-1,r), since C has n-1 elements. On the other hand, when a is a member of the set B, then B can be thought of as a union of two sets – a set D that has all the elements of B except a, and the other is just {a}. So, B = D ⋃ {a}. Now, you can see that D is a subset of C that we defined. How many such subsets D are there of C? There are choose(n-1,r-1) subsets, since C has n-1 elements and D has r-1 elements. So, the number of such subsets B is choose(n-1,r-1). This means that the total number of sets B with or without a as an element is choose(n-1,r) + choose(n-1,r-1). If we put this in recursive calls, the r and n will get reduced until r equals zero or n equals r. We have already considered the case when n equals r, that is, choose(n,n). When r equals zero, it means B is the null set. Since there is only one null set, choose(n,0) equals 1. Now, we put this in code:

public long choose(long n, long r){
  if(n<r){
    return 0;
  }else if(r==0){
    return 1;
  }else if(n==r){
    return 1;
  }else{
    return choose(n-1,r) + choose(n-1,r-1);
  }
}

That was a little complex, but note that not only did we compute the value of the choose function, we also sort of proved that it will work. The choose function is the binomial coefficient function for integral exponents.

The aforementioned implementation is not efficient. To see why, just consider what each recursive call of the choose function will evaluate to when they both fall in the final else case: choose(n-1,r) = choose(n-2,r) + choose(n-2,r-1) and choose(n-1,r-1) = choose(n-2,r-1) + choose(n-2,r-2). Now note that choose(n-2,r-1) is being evaluated in both cases, which then would have its own recursive calls. This actually significantly increases the asymptotic complexity. We'll defer the analysis of this complexity to the end of this chapter.