Threaded Mode | Linear Mode

G4143 · 08-21-2009, 12:09 PM

This one's for everyone.

Re-write this recursive function so that you can have recursion as deep as you like.

Code:

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

unsigned long addit(unsigned long x)

{

    if (x > 0)

    {

        return x + addit(x - 1);

    }

    else

    {

        return x;

    }

}

int main(int argc, char**argv)

{

    int choice;

    unsigned long val = 10;

    while (true)

    {

        fputs("(0)exit (1)try a value->", stdout);

        fscanf(stdin, "%d", &choice);

        if (choice <= 0) break;

        if (choice == 1)

        {

            fputs("enter a value->", stdout);

            fscanf(stdin, "%u", &val);

            fprintf(stdout, "ans->%u\n", addit(val));

        }

    }

    exit(EXIT_SUCCESS);

}

To see what I'm driving at try copying this program and running it. Now enter some numbers for the recursive function, eventually you'll reach a number where the recursion is too deep for the stack and you will end with a segmentation fault(this is normal).
What you need to do is re-write the recursive function so that its still “recursive” but it will not be constrained by the size of the number...G4143

An example:

On my machine if I enter the numbers 10, 100, 1000 and 10000 the recursive function works fine but if I enter 123456789 the number causes the recursive function to exhaust my stack space and crash the program...How could you re-write this recursive function, so that its still recursive but will allow all the numbers defined in unsigned long?

As far as I know - there is no right or wrong answer for this..

***drdebcol*** · 08-21-2009, 05:20 PM

I was trying to do this with big numbers, but recursion+big numbers, it is too much, only thing that i can say is to define "unsigned long long" except of "unsigned long",
i don't see another answer !

G4143 · 08-21-2009, 10:05 PM

(08-21-2009 05:20 PM)drdebcol Wrote: I was trying to do this with big numbers, but recursion+big numbers, it is too much, only thing that i can say is to define "unsigned long long" except of "unsigned long",
i don't see another answer !

The only way I can think to solve this is using threads. Each thread would solve so much of the recursive function then return its result that would be totalled in the end...G4143

G4143 · 08-22-2009, 06:32 AM

This is a quick solution. It works by splitting up the recursion into separate loops. It also has the failing, if the number is large enough, of wrapping the answer passed zero...so large numbers give inaccurate answers. A solutions to this would be to incorporated the big num library.

At the beginning I was going to solve this with threads but this answer is similar, easier and threads are a pain in the ass...G4143

I may still post the thread version.

Code:

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

unsigned long addit(unsigned int x, unsigned int times)

{

    if ((x <= 0) || (times <= 1))

    {

        return x;

    }

    else

    {

        return x + addit((x - 1), (times - 1));

    }

}

unsigned long addit2(unsigned int x, unsigned int times)

{

    unsigned long ans = 0;

    if (times > x) {times = x;}

    while (x > 0)

    {

        ans += addit(x, times);

        fprintf(stdout, "ans->%u, %u\n", ans, x);

        x -= times;

    }

    return ans;

}

int main(int argc, char**argv)

{

    unsigned long choice, val, times;

    while (true)

    {

        fputs("(0)exit (1)try->", stdout);

        fscanf(stdin, "%d", &choice);

        if (choice <= 0) break;

        if (choice == 1)

        {

            fputs("enter a number->", stdout);

            fscanf(stdin, "%u", &val);

            fputs("enter recursion times->", stdout);

            fscanf(stdin, "%u", &times);

            fprintf(stdout, "ans->%u\n", addit2(val, times));

        }

    }

    exit(EXIT_SUCCESS);

}