calgorithmrecursion

# Problem with recursive calls when x only takes t time, but when 10x it needs 100t time and much slower

I have an assignment about practicing the algorithm recursive method, and since I'm new about this, I wanted to ask about, if there's anything I could possibly do to improve the speed of my code here.

So the assignment is about making a program that output the powered of each numbers between two intervals (and let's say that the first interval is from `1`, and goes to `n`). For example, between `1 to n = 5` it should be able to output those powered numbers in between, something like: `1 4 9 16 25`. There's a little problem I encountered on my function, but since it's not a really big deal, I can just let it go by incrementing the value of `n by 1` (since the default value of `n, if n = 5` as in the shown example, it will not starts from `1`, rather from 0 and goes to `16` all the way, so I just tricked the program by thinking into going to `25` by `n = 6` because of the `0` at the start).

Since my assignment asked me to output the code not in ascending order (must be in descending order), I gotta use another method of sorting, and I chose Quick Sort method in the first place, since I'm hoping it will make the program at least not as slow as using Bubble Sort and other `log(n^2)` time complexity sorting algorithms. At the end, the performance issue's still there, and even I deleted my Quick Sort, it is still indeed as slow as it can possibly be, and I'm wondering why as the perfomance issue keep worsen at `n >= 10`... Any help will be much appreciated to improve my understandings of the recursive call algorithm methods.

Here's the code I began to work with:

``````long long int PoweredSeriesArray[BUFSIZE32];
void SwapLLInt(long long int *X, long long int *Y) { long long int Temp = *X; *X = *Y; *Y = Temp; }

long long int StairsOfPowers(long long int Value) {
long long int Result = 0;

for (int Idx = 0; Idx < Value; Idx++) {
if (Value > 1) { Result = pow(StairsOfPowers(Value - 1), 2); }
PoweredSeriesArray[Idx] = Result;
}
return Value;
}

int Partition(long long int Array[], long long int Low, long long int High, bool Ascending) {
long long int PartitionInTraversevot = Array[High];
long long int i = (Low - 1);

if (Ascending) {
for (long long int j = Low; j < High; j++) {
if (Array[j] <= PartitionInTraversevot) {
i++;
SwapLLInt(&Array[i], &Array[j]);
}
} SwapLLInt(&Array[i + 1], &Array[High]);
} else {
for (long long int j = Low; j < High; j++) {
if (Array[j] >= PartitionInTraversevot) {
i++;
SwapLLInt(&Array[i], &Array[j]);
}
} SwapLLInt(&Array[i + 1], &Array[High]);
}
return (i + 1);
}

void QuickSort(long long int Array[], long long int Low, long long int High, bool Ascending) {
if (Low < High) {
int PartitionInTraverse = Partition(Array, Low, High, Ascending);

QuickSort(Array, Low, PartitionInTraverse - 1, Ascending);
QuickSort(Array, PartitionInTraverse + 1, High, Ascending);
}
}

int main(int argc, char** argv) {
long long int PoweredUpTo;

puts("WARNING: Inserting a number >= 10, resulting in the SLOWER PROCESS because of the recursive call!\n");
printf("Insert a number to be doubled with        (max: [2^31] - 1):\n  > "); scanf("%lld", &PoweredUpTo);
puts("\nThe following results are the staircase of each integers being powered to the two.");
printf(">>> ");

// Adding by 1 to trick the function, so the result
// is able to get from 0 up to pow(PoweredUpTo + 1, 2).
// Example: if n = 5, then result is 0 1 4 9 16;
// Making sure that the powered by two of n is there,
// not just up to n - 1, trick by adding by 1 more.
// Example: if n = (5 + 1), then result is 0 1 4 9 16 25;
StairsOfPowers((PoweredUpTo + 1));

// Sorting the array in descending order, because of the
// boolean value is set to false, meaning not in ascending order.
QuickSort(PoweredSeriesArray, 0, (PoweredUpTo), false);

for (int i = 0; i < PoweredUpTo; i++) {
printf("%lld ", PoweredSeriesArray[i]);
} return 0;
}
``````

Solution

• You do not need an array to achieve your goals. You need to implement head recursion as shown in the following Ada language program.

``````with Ada.Text_IO;         use Ada.Text_IO;

procedure Main is

Min : Positive;
Max : Positive;

procedure square (value : Positive) is
begin
if value < Max then
square (value + 1);
end if;
Put_Line (value'Image & " squared is" & Positive'Image (value * value));
end square;

begin
Put ("Enter the minimum value: ");
Get (Min);
Put ("Enter the maximum value: ");
Get (Max);
square (Min);
end Main;
``````

See the following program output for a sample set of results:

``````Enter the minimum value: 1
Enter the maximum value: 10
10 squared is 100
9 squared is 81
8 squared is 64
7 squared is 49
6 squared is 36
5 squared is 25
4 squared is 16
3 squared is 9
2 squared is 4
1 squared is 1
``````

This algorithm will execute 100 * 100 just as fast as 2 * 2.