505 views

Consider the following function.

Function F(n, m:integer):integer;
begin
If (n<=0 or (m<=0) then F:=1
else
F:F(n-1, m) + F(n, m-1);
end;


Use the recurrence relation  $\begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} n-1 \\ k \end{pmatrix} + \begin{pmatrix} n-1 \\ k-1 \end{pmatrix}$  to answer the following questions. Assume that $n, m$ are positive integers. Write only the answers without any explanation.

1. What is the value of $F(n, 2)$?

2. What is the value of $F(n, m)$?

3. How many recursive calls are made to the function $F$, including the original call, when evaluating $F(n, m)$.

0

Hi,

I think question needs small correction.

F:F(n-1, m) + F(n-1, m-1);
0

People have provided good answer for A and B part. But for C part O(2^n) is upper bound. I am unable to get exact formula for number of calls for particular F(n,m). But following code could be used to get exact answer.

public class Test {
public static int n, m, numberOfRecursiveCalls;

public static int nCm(int a, int b) {
numberOfRecursiveCalls++;
if(a<=0||b<=0) return 1;
else 	return nCm(a-1, b) + nCm(a-1, b-1);
}
public static void main(String[] args) {
n = 10;  m = 9;
numberOfRecursiveCalls = 0;
nCm(n,m);
System.out.println(numberOfRecursiveCalls);
}
}


If anyone knows how exact number of calls could be calculated in Pascal's identity. Please mention it in the answer section. It will be great help.

+1 vote
a) $\frac{n(n-1)}{2}$

b) $\frac{n(n-m+1)}{m!}$
+1
@Anirudh

a) should be

$\frac{(n+1) * (n+2)}{2}$

b) I m struggling for it :p
0
Isn't its simply nCm ??

(a) nC2

(b) nCm = (n * n-1 * n-2  *....* n-m+1 ) / m!

(c) No. Of Recursive Calls = O(2^n)
+1
In program it is :
F:F(n-1, m) + F(n, m-1);

and recurence relation given :

$\begin{pmatrix} n\\ k \end{pmatrix}$  =  $\begin{pmatrix} n-1\\ k \end{pmatrix}$ + $\begin{pmatrix} n-1\\ k-1\end{pmatrix}$

Which one to consider ?

a) $(n+1)(n+2)\over2$

b) $(n+m)!\over n!m!$

c) $2{{(n+m)!}\over{n!m!}} - 1$

1
2