UVa 3n+1 Case Recursive Stack Overflow

Question

im trying to solve this very first challange but i get stuck, i like fast program, so i decided to use recursive method not iteration

unfortunately, when the input is a big integer (100000 > input > 1000000), its often crash

so i debug it, and it shows stack overflow error

please help me, i dont know what to do, ive tried to change data type to unsigned long, unsigned int, etc, but none of it works

here is my code, im using ANSI C

#include "stdio.h"

int cek(int n) {
    return n % 2;
}

int fung(int n,int c) {
    if (n == 1) {
        return c;
    }
    if (!cek(n)) {
        return fung(n/2,++c);
    }
    else {
        return fung((n*3)+1,++c);
    }
}

int comp(int i,int j,int tmp) {
    int temp;
    if (i == j)
        return tmp;
    temp = fung(i,1);
    if (temp > tmp)
        return comp(++i,j,temp);
    else
        return comp(++i,j,tmp);
}

int main() {
    int i,j,tmp;
    while (scanf("%d %d",&i,&j)) {
        if (i > j) {
            tmp = i;
            i = j;
            j = tmp;
        }
        printf("%d %d %d\n",i,j,comp(i,j,0));
    }
    return 0;
}

PS: sorry for my stupidness, im really a newbie @_@

"i like fast program, so i decided to use recursive method not iteration" - Who taught you that? Besides, you should try to like readable program better than fast programs. — polygenelubricants
– polygenelubricants, Commented Aug 11, 2010 at 7:26
Seeing temp and tmp used for the same parameter in the same function hurts my eyes. — Blindy
– Blindy, Commented Aug 11, 2010 at 7:31
Please comment your code and describe what it is supposed to do, you can do that by editing your question. If you have hidden assumptions about values, put in assertions to ensure that they hold. Also indicate more precisely for which inputs it works, for which not etc. — Jens Gustedt
– Jens Gustedt, Commented Aug 11, 2010 at 8:12

Thomas · Accepted Answer · 2010-08-11 07:10:23Z

6

Recursion is not likely to be faster than iteration, and in fact it's likely to be slower.

The call stack has a limited size, and if your recursion goes deeper than that, there's nothing you can do about it. Especially in the Collatz problem, there's no way to tell up front how many steps you'll need. Rewrite this using an iterative method instead.

(If your compiler does tail call optimization, recursion might still work. But TCO is not required by the standard, so it will lead to unportable code. And apparently, your compiler does not optimize this particular tail call anyway.)

answered Aug 11, 2010 at 7:10

Thomas

183k57 gold badges383 silver badges510 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

leppie Over a year ago

Or he might not have optimizations enabled (for TCE). Actually, that is a scary thought!

Ady Over a year ago

Thank you for your information, but outhere i saw same recursive code, but in C++ it works fine, not like mine thats why im really frustated =_= here the code unsigned int cycle(unsigned int curValue, unsigned int count) { if(curValue == 1) return count; if(isEven(curValue)) return cycle(curValue/2, count+1); else return cycle((curValue*3)+1, count+1); }

leppie Over a year ago

@Ady Putra: And what about comp?

Ady Over a year ago

@leppi ive changed it with iterative method, so only the fung recursive method left, but still...

Blindy Over a year ago

What he has isn't tail recursive.

|

mkj · Accepted Answer · 2016-11-28 13:18:30Z

2

Not a C expert, but usually there is a call stack depth limit enforced by the compiler. Probably you can change this with a compiler flag, but this will not solve your problem. Making the algorithm iterative instead of recursive will fix it.

Recursive algorithms won't go faster than iterative ones, usually. But they are typically nicer to understand. (= more elegant)

edited Nov 28, 2016 at 13:18

mkj

2,8515 gold badges25 silver badges28 bronze badges

answered Aug 11, 2010 at 7:10

jvdneste

1,6871 gold badge12 silver badges14 bronze badges

1 Comment

Thomas Over a year ago

This problem is more elegantly expressed as a simple loop, rather than a recursive function, IMHO.

Ady · Accepted Answer · 2010-08-11 11:31:05Z

-1

Okay guys, i found it!!!

so this is my code, i still use recursion but only for the inner loop fung(),

im not really impressed of it, because its need 0,5 sec to count input 1 and 1000000, someone's code outhere can do it in 0 sec, LOL

i change the outer loop comp() with iterative method,

look here

#include "stdio.h"
/*#include "windows.h"*/

int cek(int n) {
    return n % 2;
}

unsigned int fung(unsigned int n,unsigned int c) {
    if (n == 1) return c;
    if (!cek(n)) return fung(n/2,++c);
    else return fung((n*3)+1,++c);
}

/*
Above recursion will looked like this in iterative method
int func(int n) {
    int c=1;
    while (n != 1) {
        c++;
        if (n % 2 == 0)
            n=n/2;
        else
            n=(n*3)+1;
    }
    return c;
}
*/

/*Outer Loop*/
int iter(int i,int j) {
    int tmp1=0,tmp2;
    while (i <= j) {
        tmp2 = fung(i,1);
        if (tmp1 < tmp2)
            tmp1 = tmp2;
        i++;
    }
    return tmp1;
}

int main() {
    unsigned int i,j,s,f;
    while (scanf("%d %d",&i,&j)) {            /*UVa Standard, infinite loop*/
        /*s = GetTickCount();*/
        printf("%d %d %d",i,j,iter(i,j));
        /*f = GetTickCount();
        printf("%lu\n",f-s);*/
    }
    return 0;
}

answered Aug 11, 2010 at 11:31

Ady

193 bronze badges

1 Comment

Vatine Over a year ago

Please update your question, instead of answering it yourself.

Collectives™ on Stack Overflow

UVa 3n+1 Case Recursive Stack Overflow

3 Answers 3

9 Comments

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

9 Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related