Recursion problem

[FireKhan]

Hey everyone,

I'm working on an algorithm class now, and I'm trying to understand recursion better. I have a problem that that requires writing a recursive function for a problem using dynamic programming. I have come up with a standard non recursive function, to try and understand the problem better in my mind before converting this to recursion with dynamic programming. However I would like to know if my function is correct for this problem.

Pn = Pn-1 + 2Pn-2, P1 = P0 = 1

int P(int n)
{
int value = 0;

for (int a = n; a >= 2; --a)
{ value += (a - 1); }

for (int b = n; b >= 2; b = b - 2)
{ value += 2 * (b - 2); }

value += 2; // for P1 = P0 = 1

return value;
}

Am I correct on this? Thanks for any and all help!

Firekhan

 

[dougli1sqrd]

Don't you need parenthases around the arguments for your function 'P'?

And, I don't understand the first line. You haven't defined P(int n) yet. Maybe I'm not understandnig something.

These are just my thoughts. Maybe this helps at all?
Good luck.

 

[FireKhan]

What do you mean defined P(int n)? It's a C++ function.

Pn = Pn-1 + 2Pn-2, P1 = P0 = 1

is a recursive statement, not a function. I'm working on algorithm analysis.

 

[Voral]

What do you mean defined P(int n)? It's a C++ function.

Pn = Pn-1 + 2Pn-2, P1 = P0 = 1

is a recursive statement, not a function. I'm working on algorithm analysis.

Specify a question.

In your example:
Pn = -3/2; P1=P0=1;
And

double P(int n) {
 if ((n=0)||(n=1)) return 1;
 else return -1.5;
};

 

[pavan_2804]

FireKhan ....

I agree with the code above . If you have perfect non recursive funtion for your problem. What is the your algo all about ? And do you just want to resolve the problem using recursive method or trying to understand.
Anyway I dont see any questions your post.Good Luck !!

 

[FireKhan]

Pavan,
Thanks for the reply. You answered my first question, and yes, I do want to resolve it using a recursive method. However in my own mind I couldn't come up with a recursive method before I saw a loop work with it properly, which is why I wanted to know if my loop was correct. The problem is supposed to be solved with a recursive function using dynamic programming. Thanks for any help!

 

[Voral]

Recursion should look as follows (schematically):

double P (int n) {
 double Result;
 <a_necessary_code>
 if (<some_condition>) Result+=P (<some_parameter>);
 <a_necessary_code>
 return Result;
}

 

[ziedmaktouf]

the answer is

int P(int n)
{
if( (1==n)||(0==n) ) return 1;
return ( P(n-1) + 2*P(n-2) );
}

 

[mailsubhra]

quiet right I think..

if( (1==n)||(0==n) ) return 1;

But what is the need of (0==n).....

As per my understanding the code will return when n becomes 1 and hence n==0 will never be true.