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.