Recursion problem

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

  1. FireKhan

    FireKhan

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

  2. FireKhan

    dougli1sqrd

    Joined:
    Aug 11, 2006
    Messages:
    4
    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
    #2
    1. Advertising

  3. FireKhan

    FireKhan

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

    Voral

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

    In your example:
    Pn = -3/2; P1=P0=1;
    And
    Code:
    double P(int n) {
     if ((n=0)||(n=1)) return 1;
     else return -1.5;
    };
    
    Voral, Aug 13, 2006
    #4
  5. FireKhan

    pavan_2804

    Joined:
    Jul 4, 2006
    Messages:
    11
    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
    #5
  6. FireKhan

    FireKhan

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

    Voral

    Joined:
    Jul 30, 2006
    Messages:
    5
    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;
    }
    
    Voral, Aug 15, 2006
    #7
  8. FireKhan

    ziedmaktouf

    Joined:
    Aug 24, 2006
    Messages:
    1
    Location:
    Tunisia
    the answer is

    int P(int n)
    {
    if( (1==n)||(0==n) ) return 1;
    return ( P(n-1) + 2*P(n-2) );
    }
    ziedmaktouf, Sep 9, 2006
    #8
  9. FireKhan

    mailsubhra

    Joined:
    Sep 8, 2006
    Messages:
    3
    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.
    mailsubhra, Oct 5, 2006
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. kelvSYC

    Recursion-related problem

    kelvSYC, Nov 18, 2003, in forum: Java
    Replies:
    2
    Views:
    313
    Eric Sosman
    Nov 18, 2003
  2. Anakin
    Replies:
    14
    Views:
    742
    Thomas G. Marshall
    Apr 13, 2005
  3. JimC
    Replies:
    3
    Views:
    513
  4. Allan W
    Replies:
    4
    Views:
    521
    Jos A. Horsmeier
    Jan 22, 2004
  5. jononanon@googlemail.com

    va_arg... recursion: changing arguments and the using recursion

    jononanon@googlemail.com, Apr 25, 2012, in forum: C Programming
    Replies:
    8
    Views:
    723
    John Reye
    Apr 26, 2012
Loading...

Share This Page