Consider the following recursive function: public static int f ( int n ) { if (

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

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.