Question

Consider the following recursive method: public int someFun(int n) { if (n <= 0) return 2; else return someFun(n-1) * someFun(n-1); } (a) When the program calls someFun(5), how many times will someFun(3) be called? (b) What does this method calculate when the input parameter n is a non-negative integer?

Answer 1

Answer:

(a) someFunc(3) will be called 4 times.

(b) For non negative number n someFunc method calculates 2^2^n.

Explanation:

When you call someFunc(5) it will call someFunc(4) two time.

So now we have two someFunc(4) now each someFunc(4) will call someFunc(3) two times.Hence the call to someFun(3) is 4 times.

someFunc(n) calculates someFunc(n-1) two times and calculates it's product.

someFunc(n) = someFunc(n-1)^2..........(1)

someFunc(n-1)=someFunc(n-2)^2..........(2)

substituting the value form eq2 to eq 1.

someFunc(n)=someFunc(n-2)^2^2

       .

       .

       .

       .

= someFunc(n-n)^2^n.

=2^2^n

2 raised to the power 2 raised to the power n.