Thread: A recurrsion qs

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    15

    A recurrsion qs

    I am trying to understand the following Algorithm. It is a recursive algorithm but i am confused whether the two for loops are nested?
    or first i will run 3n times then condition for n>1 will be checked.
    This is pseudocode form, not exactly in C.

    Code:
    PrintAs (n : integer)
    for i 1 to 3n do print(“A”)
    if n>1then: forj1to4 doPrintAs[floor(n/3)] 
    As far as I understand it, if n is 3, i will go from 1 to 9, then condition for n will be checked, since 3>1, PrintAs will be called recursively 4 times.
    Please correct me if i am wrong.
    thanks

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Given that pseudocode is not precisely defined, I can understand your confusion.

    My guess is that the loops are not nested, since the control variable from the first loop (i) is not used in the second (within the third line).

    The only way to be sure is to do a sanity check using a description of what the algorithm achieves (i.e. the result it produces, rather than how it does it).
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  3. #3
    Registered User
    Join Date
    Nov 2012
    Posts
    1,393
    Algorithms can be analyzed until you're blue in the face. But this is a C programming forum, so just convert it to C and try it out:

    Code:
    void PrintAs(int n) {
        for (int i=1; i <= 3*n; i++)
            putchar('A');
        if (n>1)
            for (int j=1; j <= 4; j++)
                PrintAs(n/3);  
    }
    Note that floor(n/3) is the same as n/3 in C because we're doing integer division, so floor() operation is done implcitly.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem with recurrsion
    By newbie123 in forum C Programming
    Replies: 6
    Last Post: 09-01-2010, 05:39 PM

Tags for this Thread