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;
with Ada.Integer_Text_IO; use Ada.Integer_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.

- Passing the function *cmp(const *void, const *void) as a parameter in C and using it to create a queue?
- Is it safe to use `strstr` to search for multibyte UTF-8 characters in a string?
- Why am I getting a heap-use-after-free error?
- Catch and compute overflow during multiplication of two large integers
- Access a global static variable from another file in C
- "this" pointer in C (not C++)
- Unknown Output of C code
- Yocto- gcc cannot find shared library
- Artifact in one of the triangles in basic OpenGL texture quadrilateral
- How to check if a pointer is valid?
- cJSON Key-Value Parsing
- hi, I am emplementing LZW here and it work great, the problem is that I cant scan and encode a string if it have a (space)
- pthread clean up int/array/struct type variables using pthread_cleanup_push
- Standard way of getting a bit pattern of all ones
- Why doesn't the use of strictly conforming programs and conforming implementations ensure absolute portability?
- Checking emptiness of X macros
- Is it possible to run WebAssembly code async?
- C suddenly messing up values in 2d array
- Socket opening macOS assembly
- GDB outputs arm mnemonics
- What kind of optimization does const offer in C/C++?
- wcstombs segmentation fault
- Fast implementation of complementary error function with 5-digit accuracy
- Ascii to binary calculation is flawed
- what stops GCC __restrict__ qualifier from working
- Why my sig_int() function can't prevent my function from exit in c?
- Allocating user space memory in Linux Kernel
- Determining realloc() behaviour before calling it
- Is it legal to cast a struct to an integer if it has no padding?
- C macro, something weird