A recurrsion qs

This is a discussion on A recurrsion qs within the C Programming forums, part of the General Programming Boards category; I am trying to understand the following Algorithm. It is a recursive algorithm but i am confused whether the two ...

  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,246
    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%.

  3. #3
    Registered User
    Join Date
    Nov 2012
    Posts
    1,057
    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


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21