// The mth Bernoulli number B(m) is defined recursively as follows:
// 
// B(m) = 1 - sum of all (k = 0 to m - 1) of { (m choose k) * B(k) / (m - k + 1) }
// 
// The base case is B(0) = 1.
// 
// Write a program to compute the first 10 Bernoulli numbers.

// Author:rahule@cse.iitk.ac.in

#include<stdio.h>
float Bernoulli_number(int);
int choose(int,int);
main()
{
  int i;
  printf("\nThe first 10 Bernoulli numbers are as follows...\n");
  for(i=0;i<10;i++)		//for each i,prints Bernoulli number(i).ie B(0),B(1)....B(9)
    printf("B(%d): %f\n",i,Bernoulli_number(i));
}


float Bernoulli_number(int m)		
//funcation to that accepts m as argument and returns B(m)
{
  int k;
  float sum=0;
  if(m==0)		//base case;if m=0,then return 1
    return(1);
    else
    {
      for(k=0;k<m;k++)
	sum=sum+choose(m,k)*Bernoulli_number(k)/(m-k+1);		//calculates sum of all (k = 0 to m - 1) of { (m choose k) * B(k) / (m - k + 1) }
      return(1-sum);		//returns 1-sum of all (k = 0 to m - 1) of { (m choose k) * B(k) / (m - k + 1) }
    }
}

int choose(int m,int k)  
//function to calculate the combination.Given two arguements m,k it calculates C(m,k)
{
  int temp1=1,temp2=1,i;
  for(i=0;i<k;i++)
  {
    temp1=temp1*(m-i);		//calculates m*(m-1)(m-2)....(m-k+1)
    temp2=temp2*(i+1);		//calculates k!
  }
  return(temp1/temp2);		//returns C(m,k)
}