-
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: forj←1to4 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
-
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).
-
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.