Can anyone tell what is the difference between these two questions. both looks same apparantely…

2,114 views

Consider the function $F(n)$ for which the pseudocode is given below :

Function F(n) begin F1 ← 1 if(n=1) then F ← 3 else For i = 1 to n do begin C ← 0 For j = 1 to n – 1 do begin C ← C + 1 end F1 = F1 * C end F = F1 end

[$n$ is a positive integer greater than zero]

- Derive a recurrence relation for $F(n)$.

### 1 comment

## 4 Answers

Best answer

- The function $F(n)$ is NOT a recursive function. You can't have a recurrence relation for it in the first place!
- $F(n)$ calculates $(n-1)^n$.

The equivalent C++ code is as follows: (You can try it out here: http://ideone.com/w0u4lk)

long F(long n) { long F1 = 1; if(n==1) { return 3; } else { for(long i = 1; i <= n; i++) { long C = 0; // Note: the belore For loop only has one line for(long j = 1; j <= n-1; j++) { C = C+1; } // At the end of this for loop, C will be = (n-1) F1 = F1 * C; } } return F1; }

It is clear that the inner for loop can be replaced by a single statement as follows:

long F(long n) { long F1 = 1; if(n==1) { return 3; } else { for(long i = 1; i <= n; i++) F1 = F1 * (n-1); } return F1; }

And this calculates $(n-1)^n$