
タイトル：
0129 Recurrence Relation

概説：

What we're going to do right now is a recurrence relation,

which is a kind of recursive mathematical function,

which is a good match for this recursive algorithmic expression for Rec_Russian

Rec_Russian recurrence relation.

Looking at the structure of Rec_Russian, if a is 0, then it's going to execute 1 statement

basically the test to see whether it’s 0 and returns.

Otherwise, if a is bigger than 0 and even, let's take a look at what Rec_Russian does in that case.

We come in here with a number that is even and greater than 0 is going to execute

the condition of this if statement, which fails so there's 1 of that.

Then 1 more to do this plus it's going to recursively workout the value of this quantity.

Then one more operation to multiply that by 2.

I call a total of 3 plus however long it takes to multiply a over 2 times b.

We don't know what that is.

We're imaging that we're going be able to create a function T

that is going to give us the answer to that.

Let's just leave it at that for now.

Finally, in the case where a is odd, it's going to execute the condition of this if statement,

the condition of this if statement, both of which will fail.

Then it will recursively compute the product, and then basically execute the returns.

A total of 3 statements plus however long it takes to do the recursive call

so 3 statements plus this particular kind of recursive call.

This now is a mathematical specification of a function.

We don't know at the moment what the relationship is between a and T(a),

but at least it's fully specified.

It turns out that you actually can solve this pretty easily

by using what we already worked out about the number of times

you can divide a number a in half, rounding down if it's odd,

before you get down to 0.

See if you can put that together to try to answer the question

what does T(a) equal from these set of choices.