Consider the following recursive function: public static int f ( int n ) { if (
ID: 3594167 • Letter: C
Question
Consider the following recursive function:
public static int f ( int n ) {
if ( n > 1000 )
return n - 4;
return f ( f (n + 5) ); }
b) Either exhibit an input instance n on which a call to f(n) gets into infinite recursion, or argue that on all n, f(n) terminates after a finite number of steps. [You may answer this in conjunction with part (c) below.] c) For an arbitrary given n, what does f(n) return (if it terminates) ? Express your answer in its simplest form as a function of n. d) What is the exact number of calls to f() made by a call to f(n) (finite? ) ? Express your answer in its simplest form as a function of n.
[Hint: use “backwards” mathematical induction. What are the base cases?]
Explanation / Answer
For n > 1000, f(n) = n - 4
Let stepf(n) gives total number of steps taken to evaluate f(n).
For n > 1000 this is 1.
Now lets play with few numbers.
f(1001) = 997, stepsf(1001) = 1
f(1000) = f(f(1005)) = f(1001) = 997, stepsf(1000) = 3
f(999) = f(f(1004)) = f(1000) = 997, stepsf(999) = 5
Thus suggests, stepsf(n) = stepsf(n+1) + 2
stepsf(1000) = 3
stepsf(999) = 5
stepsf(998) = 7
So, steps(1000-i) = 3 + i*2
So, stepsf(n) = 2001 + (n-1)*2 = 2n + 1999 for n <= 1000
and stepsf(n) = 1 for n > 1000
and f(n) = 997 for n <= 1000
f(n) = n - 4 for n > 1000