f(n), understanding the equation

Question

I've been tasked with writing MIPS instruction code for the following formula:

f(n) = 3 f(n-1) + 2 f(n-2)  
f(0) = 1
f(1) = 1

I'm having issues understanding what the formula actually means.

From what I understand we are passing an int n to the doubly recursive program.

So for f(0) the for would the equation be:

f(n)=3*1(n-1) + 2*(n-2)

If n=10 the equation would be:

f(10)=3*1(10-1) + 2*(10-2)

I know I'm not getting this right at all because it wouldn't be recursive. Any light you could shed on what the equation actually means would be great. I should be able to write the MIPS code once I understand the equation.

Answer 1

I think it's a difference equation.

You're given two starting values:

f(0) = 1
f(1) = 1
f(n) = 3*f(n-1) + 2*f(n-2)

So now you can keep going like this:

f(2) = 3*f(1) + 2*f(0) = 3 + 2 = 5
f(3) = 3*f(2) + 2*f(1) = 15 + 2 = 17

So your recursive method would look like this (I'll write Java-like notation):

public int f(n) {
    if (n == 0) {
        return 1;
    } else if (n == 1) {
        return 1; 
    } else { 
        return 3*f(n-1) + 2*f(n-2); // see? the recursion happens here.
    }
}

Answer 2

You have two base cases:

f(0) = 1
f(1) = 1

Anything else uses the recursive formula. For example, let's calculate f(4). It's not one of the base cases, so we must use the full equation. Plugging in n=4 we get:

f(4) = 3 f(4-1) + 2 f(4-2) = 3 f(3) + 2 f(2)

Hm, not done yet. To calculate f(4) we need to know what f(3) and f(2) are. Neither of those are base cases, so we've got to do some recursive calculations. All right...

f(3) = 3 f(3-1) + 2 f(3-2) = 3 f(2) + 2 f(1)
f(2) = 3 f(2-1) + 2 f(2-2) = 3 f(1) + 2 f(0)

There we go! We've reached bottom. f(2) is defined in terms of f(1) and f(0), and we know what those two values are. We were given those, so we don't need to do any more recursive calculations.

f(2) = 3 f(1) + 2 f(0) = 3×1 + 2×1 = 5

Now that we know what f(2) is, we can unwind our recursive chain and solve f(3).

f(3) = 3 f(2) + 2 f(1) = 3×5 + 2×1 = 17

And finally, we unwind one more time and solve f(4).

f(4) = 3 f(3) + 2 f(2) = 3×17 + 2×5 = 61

Answer 3

No, I think you're right and it is recursive. It seems to be a variation of the Fibonacci Sequence, a classic recursive problem

Remember, a recursive algorithm has 2 parts:

1. The base case
2. The recursive call

The base case specifies the point at which you cannot recurse anymore. For example, if you are sorting recursively, the base case is a list of length 1 (since a single item is trivially sorted).

So (assuming n is not negative), you have 2 base cases: n = 0 and n = 1. If your function receives an n value equal to 0 or 1, then it doesn't make sense to recurse anymore

With that in mind, your code should look something like this:

function f(int n):
    #check for base case

    #if not the base case, perform recursion

So let's use Fibonacci as an example.

In a Fibonacci sequence, each number is the sum of the 2 numbers before it. So, given the sequence 1, 2 the next number is obviously 1 + 2 = 3 and the number after that is 2 + 3 = 5, 3 + 5 = 8 and so on. Put generically, the nth Fibonacci number is the (n - 1)th Fibonacci Number plus the (n - 2)th Fibonacci Number, or f(n) = f(n - 1) + f(n - 2)

But where does the sequence start? This is were the base case comes in. Fibonacci defined his sequence as starting from 1, 1. This means that for our pruposes, f(0) = f(1) = 1. So...

function fibonacci(int n):
    if n == 0 or n == 1:
        #for any n less than 2
        return 1

    elif n >= 2:
        #for any n 2 or greater
        return fibonacci(n-1) + fibonacci(n-2)

    else:
        #this must n < 0
        #throw some error

Note that one of the reasons Fibonacci is taught along with recursion is because it shows that sometimes recursion is a bad idea. I won't get into it here but for large n this recursive approach is very inefficient. The alternative is to have 2 global variables, n1 and n2 such that...

n1 = 1
n2 = 1

print n1
print n2

loop:
    n = n1 + n2
    n2 = n1
    n1 = n

    print n

will print the sequence.