UVa 3n+1 Case Recursive Stack Overflow

Question

hi, 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 @_@

Answer 1

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 algortihm 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)

Answer 2

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.)

Answer 3

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;
}