CODEWITHSUNDEEP
java
Nikolai Naidenov
Nikolai Naidenov

Reputation: 37

Understanding a recursive method for finding binomial coefficient

While trying to solve an assignment for finding the coefficient of a binomial using a recursive method, I came up with this:

public class Binomial
{
   public static long binom(int n, int k)
   {
       if (k==n || k==0)
         return 1;
       else return binom(n-1,k-1) + binom(n-1, k);
  }

For n=5; k=3 the method returns a value of 10. Tried it with a bunch of different values for k and n, they all gave the expected results, therefore the code works, I just have no idea why and how. I'd be very grateful for a dumbed-down explanation. Thanks!

Upvotes: 1

Views: 8706

Answers (3)

SaraVF
SaraVF

Reputation: 312

As said in the comments and other answers, in wikipedia you can see that the recursive formula can be understood with Pascal's triangle.

You can think about binom (n, k) as the total possibilities of "choosing k elements from a set of n). Lets say that you have a set of n-1 elements and you know all the different combinations about choosing any number of them (0,1, 2, 3, 4,..., n-1). A friend comes and gives you a new element. Now you have n elements and want to know the number of combinations for k elements with the new set. There are now 2 possibilities: - k is 0 or n (no element or all the elements): just one possibility. - k is another number: you can use the new element and k-1 elements from the n-1 element set you had at the beginning (remember you already new that number, taking k-1 out of n-1 elements) or you can use only elements from the set you had at the beginning (taking k out of n-1 elements).

Therefore you can say that P(n,k) = P(n-1, k-1) + P(n-1, k) when n != k and k != 0 and you can understand your code.

Upvotes: 2

Marko Topolnik
Marko Topolnik

Reputation: 200296

This is Pascal's triangle, a visualization of the binomial coefficients and their calculation:

     1
    1 1
   1 2 1
  1 3 3 1

Each element is the sum of the two above it.

Now if you take a look at your recursive formula, binom(n, k) = binom(n-1,k-1) + binom(n-1, k), taking n as the row number and k as the position of an element within the row, you'll find exactly the above rule written down in algebraic form. The only further thing you need are the boundary cases, covered by the "then" clause of your if-else statement.

Upvotes: 7

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727027

In order to prove that this recursive method works, you must prove two things:

  • That the method returns the correct value in the base case (i.e. when k is either n or zero), and
  • That an assumption that the method returns the correct value for m = n-1 implies that the method would work for n as well.

The first statement is trivially correct (the if statement does it).

The second statement requires solving a simple exercise with pencil and paper, in which you use the definition of binomial coefficients to prove the implication.

This method of constructing mathematical proofs is called mathematical induction. It is especially useful for reasoning about recursive methods in programming. Once your understanding of mathematical induction, and especially the reasons why it works, becomes solid, you would have no problem constructing your own recursive methods, and have much better chances at understanding recursive methods written by others.

Upvotes: 1

Related Questions