Writing a recurrence relation for a method

Question

I have a bit of code and need to write a recurrence relation for it. The code simply calculates 2 raised to the nth power. Any help is appreciated.

public static int two(int n) {

     if (n==0) {
       return 1;
     } else if (n%2 == 0) {
       int x = two(n/2);
       return x*x;
     } else { 
       return 2 * two(n-1)
}

Answer 1

The formulation of the function almost is a recurrence relation. Basically, all you need to do is perform a change of variables so the argument to two in the recursion is n. For example, take the following Fibonacci function:

public static int fib(n) {
    if (n==0) {
        return 1;
    } else if (n==1) {
        return 1;
    } else {
        return fib(n-1) + fib(n-2);
    }
}

You wouldn't want to use that implementation, since it's horribly inefficient, but it makes writing the recurrence relation easy:

fib0=1
fib1=1
fibn+2 = fibn+1 + fibn

With the fibonacci example, you don't actually need to perform the change of variables. However, with your two function, it will make it simpler to write the relation.