Recursive problem

[Jussi Piitulainen]

ahmed writes:

> So we had to do a project for our python class and we came across a
> recursive problem. The code we had to write was as follows:
> 
> T(n)
> if n == 1
> return 1
> else
> for any number(k) between 1 and n - 1
> 2 * T(n-k) + 2^i - 1
> 
> from this we need to get the minimum number which would be produced
> depending on k. I don't know how to go about doing this. Any help
> would be appreciated.

A first step would be to put that pseudocode in a form that is closer
to Python. I think it is meant as a definition of a function, T(n),
where n is a positive integer. Indentation would help, and the else
branch needs a return statement. Throw in the def T(n), too.

The function min(T(n)) does not depend on k, but it depends on i.
What's i? (Looks like the logarithm of a red herring to me.)

The crucial question, however, is what to do with the choice of k in
the else branch. You could pick a random integer in the range, making
T a random function, and then do a number of rounds to get a possible
minimum. Look up the module "random" for this, methods randint and
randrange there.

Or you could make T a generator function so that T(n) would generate
all possible values. Look up the keyword "yield" for this. It goes in
the place of "return". (This is the easiest change, and may well be
what the instructor intends.)

With a generator function, you can actually write min(T(n)), or "for m
in T(n): print(m)", or "list(T(n)", and so on.

As to recursion, you should be able to say why the function is
guaranteed to terminate. Perhaps you've covered this in class.