c programming urgent

Section A: Factorial

An example of a recursive function is factorial

factorial(0) = 1 (Base Case)

factorial(n) = n * factorial (n-1 ) (Recursive Step)

The function can be written as below:

int factorial(int n)

{

if (n==0)

return 1;

else

return n * factorial(n-1);

}

1. Rewrite the combination program below to include the recursion function.

Consider the following program that determines the combination:

Nk=N!k!N-k!

#include

// Function declaration

int fact(int);

// Main

int main(void)

{

int N, k, p;

// Input values of N and k

printf("Enter the values of N and k: ");

scanf("%d %d", &N, &k);

// Determining the values of N choose k.

p = fact(N)/(fact(k)*fact(N-k));

printf("%d", p);

return 0;

}

// Factorial Function

int fact(int x)

{

int prod = 1, i;

for (i=x; i>1; i--)

prod = prod*i;

return prod;

}

2. One problem with using the above binomial coefficient formula is that n! grows very fast and overflows an integer representation before you can do the division to bring the value back to a value that can be represented. Fortunately, another way to view C(N, k) by the following formula:

Nk=N-1k-1+N-1k

Write down the base case and recursive step. Then implement the recursive divide-and- conquer binomial coefficient function using the above equation. Call your function C(n, k).