C#•3y ago

How to deal with stack overflow error [Answered]

So when doing some programming competitions, i often get stack overflow, when doing recursion and the only way (i know about) to not get stack overflow is to not do deep recursion, but i was wondering, if there is any other way, as i kinda need recursion this time.

23 Replies

Pobiega•3y ago

Your recursion must be very deep for it to give stack overflows

Binto86OP•3y ago

yea well programming competitions \ ("/) / umm if i create a property with getter, i guess that won't work? update it didnt work

Pobiega•3y ago

a getter is a method, so yeah

Binto86OP•3y ago

yea i thought so, i just tried it, it was easy to change

Tvde1•3y ago

properties ideally shouldn't have weird logic in getters and setters

i love cat(mull-rom splines)•3y ago

use a stack

canton7•3y ago

Any recursive function can be rewritten as an iterative one. Sometimes the transformation is easy; sometimes it's less so. See this, and the follow-up part 2: https://ericlippert.com/2018/12/03/removing-a-recursion-in-python/

ericlippert

Fabulous adventures in coding

Removing a recursion in Python, part 1

For the last two decades or so I’ve admired the simplicity and power of the Python language without ever actually doing any work in it or learning about the details. I’ve been taking a …

i love cat(mull-rom splines)•3y ago

1d dp is easier with recursion + memoization, multidimensional dp is easier with tabulation

Tvde1•3y ago

it's unlikely you get stackoverflow errors if you haven't made a mistake in your recursive function make sure you don't recurse too much

MODiX•3y ago

Rwussiya#5821

REPL Result: Success

void Main()
{
    const int iters = 1_000_000_000;
    Console.WriteLine(RepI(iters));
}

int RepI(int i)
{
    if(i <= 0) return i;    
    return i * i + RepI(i - 1);
}

void Main()
{
    const int iters = 1_000_000_000;
    Console.WriteLine(RepI(iters));
}

int RepI(int i)
{
    if(i <= 0) return i;    
    return i * i + RepI(i - 1);
}

Compile: 539.326ms | Execution: 48.332ms | React with ❌ to remove this embed.

i love cat(mull-rom splines)•3y ago

well that sucks anyways, take the above function, change no approach whatsoever but use a stack instead and you get

MODiX•3y ago

Rwussiya#5821

REPL Result: Success

void Main()
{
    const int iters = 1_000_000_000;
    Console.WriteLine(RepIStack(iters));
}

int RepIStack(int i)
{
    var stack = new Stack<(int, int)>();    
    stack.Push((i, 0));
    while(stack.Count >= 0)
    {
        var (cur, ret) = stack.Pop();
        if(cur <= 0) return ret;
        stack.Push((cur - 1, cur * cur + ret));
    }
    
    return 0;
}

void Main()
{
    const int iters = 1_000_000_000;
    Console.WriteLine(RepIStack(iters));
}

int RepIStack(int i)
{
    var stack = new Stack<(int, int)>();    
    stack.Push((i, 0));
    while(stack.Count >= 0)
    {
        var (cur, ret) = stack.Pop();
        if(cur <= 0) return ret;
        stack.Push((cur - 1, cur * cur + ret));
    }
    
    return 0;
}

Compile: 667.936ms | Execution: 66.606ms | React with ❌ to remove this embed.

i love cat(mull-rom splines)•3y ago

you are emulating the stack frame with Stack<(int, int)>, which is a heap alloc object so it'll be way more than 1 or 4mb of stack or change the approach and you get

MODiX•3y ago

Rwussiya#5821

REPL Result: Success

void Main()
{
    const int iters = 1_000_000_000;
    Console.WriteLine(RepIBottomUp(iters));
}

int RepIBottomUp(int i)
{
    var ret = 0;
    for(var k = 0; k <= i; k++)
        ret += k * k;
        
    return ret;
}

void Main()
{
    const int iters = 1_000_000_000;
    Console.WriteLine(RepIBottomUp(iters));
}

int RepIBottomUp(int i)
{
    var ret = 0;
    for(var k = 0; k <= i; k++)
        ret += k * k;
        
    return ret;
}

Compile: 566.872ms | Execution: 59.246ms | React with ❌ to remove this embed.

i love cat(mull-rom splines)•3y ago

obviously doesnt work because overflow

Binto86OP•3y ago

i thought about using stack datastructure, my problem is that this is not normal recursion, i am calling the same method, but in different class instance, and i don't think i can implement this using stack?

i love cat(mull-rom splines)•3y ago

can we see the problem?

Binto86OP•3y ago

sure:

class Potion
{
    public int Preparation { get; set; }
    public int Id { get; set; }
    public List<Potion> Dependencies { get; set; } = new();
    bool alreadyRun = false;
    public int PreparationStart { get; set; } = -1;
 
    public int Prepare()
    {
        if (Dependencies.Count == 0)
        {
            PreparationStart = 0;
            return Preparation;
        }
            
        else
        {
            if(PreparationStart != -1)
            {
                return PreparationStart + Preparation;
            }
            int maxPrepTime = 0;
            for (int i = 0; i < Dependencies.Count; i++)
            {
                int prepTime = Dependencies[i].Prepare(); 
                if (prepTime>maxPrepTime)
                    maxPrepTime = prepTime;
            }

            int prepEnd = maxPrepTime + Preparation;
            PreparationStart = maxPrepTime;
            return prepEnd;
        }
    }
}

class Potion
{
    public int Preparation { get; set; }
    public int Id { get; set; }
    public List<Potion> Dependencies { get; set; } = new();
    bool alreadyRun = false;
    public int PreparationStart { get; set; } = -1;
 
    public int Prepare()
    {
        if (Dependencies.Count == 0)
        {
            PreparationStart = 0;
            return Preparation;
        }
            
        else
        {
            if(PreparationStart != -1)
            {
                return PreparationStart + Preparation;
            }
            int maxPrepTime = 0;
            for (int i = 0; i < Dependencies.Count; i++)
            {
                int prepTime = Dependencies[i].Prepare(); 
                if (prepTime>maxPrepTime)
                    maxPrepTime = prepTime;
            }

            int prepEnd = maxPrepTime + Preparation;
            PreparationStart = maxPrepTime;
            return prepEnd;
        }
    }
}

basically i have some potions that must wait until some other are finished (as i said already, its coding comepetition, i don't want any hints on what i am doing wrong, what is not as optimized as it could etc. i want to figure that out on my own)

i love cat(mull-rom splines)•3y ago

this seems like... a dp problem more than anything without further info, you seem to be bruteforcing it if you insist, the first step would be to turn this into a static function

Binto86OP•3y ago

i kinda can't as i am working with instance specific data but i will try it using stack, thanks for helping

i love cat(mull-rom splines)•3y ago

here:

    public static int Prepare(Potion potion)
    {
        if (potion.Dependencies.Count == 0)
        {
            potion.PreparationStart = 0;
            return potion.Preparation;
        }
            
        else
        {
            if(potion.PreparationStart != -1)
            {
                return potion.PreparationStart + potion.Preparation;
            }
            int maxPrepTime = 0;
            for (int i = 0; i < potion.Dependencies.Count; i++)
            {
                int prepTime = Prepare(potion.Dependencies[i]); 
                if (prepTime>maxPrepTime)
                    maxPrepTime = prepTime;
            }

            int prepEnd = maxPrepTime + potion.Preparation;
            potion.PreparationStart = maxPrepTime;
            return prepEnd;
        }
    }

    public static int Prepare(Potion potion)
    {
        if (potion.Dependencies.Count == 0)
        {
            potion.PreparationStart = 0;
            return potion.Preparation;
        }
            
        else
        {
            if(potion.PreparationStart != -1)
            {
                return potion.PreparationStart + potion.Preparation;
            }
            int maxPrepTime = 0;
            for (int i = 0; i < potion.Dependencies.Count; i++)
            {
                int prepTime = Prepare(potion.Dependencies[i]); 
                if (prepTime>maxPrepTime)
                    maxPrepTime = prepTime;
            }

            int prepEnd = maxPrepTime + potion.Preparation;
            potion.PreparationStart = maxPrepTime;
            return prepEnd;
        }
    }

then next would be to create a Stack<(int, Potion)> and reimplement there

Binto86OP•3y ago

oh like this ok, well thanks

Accord•3y ago

✅ This post has been marked as answered!

Gaming

Programming

How to deal with stack overflow error [Answered]