# Recursion problem

Discussion in 'C Programming' started by FireKhan, Aug 11, 2006.

1. ### FireKhan

Joined:
Aug 11, 2006
Messages:
3
0
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

FireKhan, Aug 11, 2006

2. ### dougli1sqrd

Joined:
Aug 11, 2006
Messages:
4
0
Location:
Oregon
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.

dougli1sqrd, Aug 11, 2006

3. ### FireKhan

Joined:
Aug 11, 2006
Messages:
3
0
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.

FireKhan, Aug 12, 2006
4. ### Voral

Joined:
Jul 30, 2006
Messages:
5
0
Specify a question.

Pn = -3/2; P1=P0=1;
And
Code (Text):

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

Voral, Aug 13, 2006
5. ### pavan_2804

Joined:
Jul 4, 2006
Messages:
11
0
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 !!

pavan_2804, Aug 14, 2006
6. ### FireKhan

Joined:
Aug 11, 2006
Messages:
3
0
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!

FireKhan, Aug 14, 2006
7. ### Voral

Joined:
Jul 30, 2006
Messages:
5
0
Recursion should look as follows (schematically):
Code (Text):

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

Voral, Aug 15, 2006
8. ### ziedmaktouf

Joined:
Aug 24, 2006
Messages:
1
0
Location:
Tunisia

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

ziedmaktouf, Sep 9, 2006
9. ### mailsubhra

Joined:
Sep 8, 2006
Messages:
3
0
quiet right I think..
Code (Text):
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.

mailsubhra, Oct 5, 2006