Velocity Reviews > C++ > Recursion problem

# Recursion problem

FireKhan
Junior Member
Join Date: Aug 2006
Posts: 3

 08-11-2006
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
Junior Member
Join Date: Aug 2006
Location: Oregon
Posts: 4

 08-11-2006
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
Junior Member
Join Date: Aug 2006
Posts: 3

 08-12-2006
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
Junior Member
Join Date: Jul 2006
Posts: 5

 08-13-2006
Quote:
 Originally Posted by 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.
Specify a question.

Pn = -3/2; P1=P0=1;
And
Code:
```double P(int n) {
if ((n=0)||(n=1)) return 1;
else return -1.5;
};```

pavan_2804
Junior Member
Join Date: Jul 2006
Posts: 11

 08-14-2006
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
Junior Member
Join Date: Aug 2006
Posts: 3

 08-14-2006
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
Junior Member
Join Date: Jul 2006
Posts: 5

 08-15-2006
Recursion should look as follows (schematically):
Code:
```double P (int n) {
double Result;
<a_necessary_code>
if (<some_condition>) Result+=P (<some_parameter>);
<a_necessary_code>
return Result;
}```

ziedmaktouf
Junior Member
Join Date: Aug 2006
Location: Tunisia
Posts: 1

 09-09-2006

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

mailsubhra
Junior Member
Join Date: Sep 2006
Posts: 4

 10-05-2006
quiet right I think..
Code:
`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.

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post jononanon@googlemail.com C Programming 8 04-26-2012 08:37 PM Anakin Java 14 04-13-2005 03:10 AM Allan W C++ 4 01-22-2004 02:42 PM JimC C++ 3 01-17-2004 12:43 PM kelvSYC Java 2 11-18-2003 03:32 PM