avoid stack over flow c++

Question

It is a program generated by another system, therefore it could be repetitive and less efficient or intelligent that it should be. The finding is it have a large dependency and fell into a deep recursive function.

Because the vector could goes to 1000 elements and it must be contiguous. The Call stack while crash "Calculation::getItem(9)" > "Calculation::getItem(8)" > "Calculation::getItem(7)" > "Calculation::getItem(6)"... It crash before return the correct result of 100.

New question is : Any ways to resolve stack overflow without increasing stack size or changing the design of recursive function.

Calculation.cpp

std::optional<std::any> Calculation::getItem(int rowNo)
{
    if(calculatedRow[rowNo].has_value())
    {
      return calculatedRow[rowNo];
    }
    switch(rowNo)
    {
        case 0 : return calculatedRow[rowNo] = 0;
        case 1 : return calculatedRow[rowNo] = 100;
        case 2 : return calculatedRow[rowNo] = getItem(1)
        case 3 : return calculatedRow[rowNo] = getItem(2)
        case 4 : return calculatedRow[rowNo] = getItem(3)
        case 5 : return calculatedRow[rowNo] = getItem(4);
        case 6 : return calculatedRow[rowNo] = getItem(5)
        case 7 : return calculatedRow[rowNo] = getItem(6);
        case 8 : return calculatedRow[rowNo] = getItem(7);
        case 9 : return calculatedRow[rowNo] = getItem(8);
...
    }
    return 0;
}

Calculation.h

namespace Calculation
{
    //private namespace
    namespace
    {
       std::vector<std::optional<std::any>> calculatedRow(1000);
    }

    std::optional<std::any> getItem(int rowNo);
};

Doesn't have to be the vector. Recursion isn't free, it costs call stack space. If you have a particularly deep call stack then that space may be exhausted by further recursion. — StoryTeller - Unslander Monica, Nov 13 '19 at 06:07
Thanks for the replied, never think of recursion could be an expensive method. — user1151874, Nov 13 '19 at 06:18
When your C++ Segfaults it's *never* a memory issue, it's always one's own fault. — nada, Nov 13 '19 at 06:38
@nada The secret society of CS 101 processors obsessed with teaching recursion surely shares some of the fault. — parktomatomi, Nov 13 '19 at 06:44
@parktomatomi especially recursion as egregious as "count the integers" — Caleth, Nov 13 '19 at 09:51

score 2 · Answer 1 · answered Nov 13 '19 at 06:50

I modified your code a little bit and run it. When I run it with a very huge number 1024 * 128 - 1 I got an error. So, I think your error is related to call stack limit. My deduction is due to you are using recursion, you are exceeding the call stack limit and program crashes. I want to share useful question and my code below.

Calculation.h

#include <optional>
#include <any>
#include <vector>

namespace Calculation {
    //private namespace
    namespace {
        std::vector<std::optional<std::any>> calculatedRow(1024 * 128);
    }

    std::optional<std::any> getItem(int rowNo);
};

Calculation.cpp

#include <optional>
#include <any>
#include <iostream>
#include "Calculation.h"


std::optional<std::any> Calculation::getItem(int rowNo) {
    std::cout << rowNo << std::endl;
    if (calculatedRow[rowNo].has_value()) {
        return calculatedRow[rowNo];
    }
    switch (rowNo) {
        case 0 :
            return calculatedRow[rowNo] = 0;
        case 1 :
            return calculatedRow[rowNo] = 100;
    }
    return calculatedRow[rowNo] = getItem(rowNo - 1);
}

main.cpp

#include "Calculation.cpp"

int main() {
//    auto retVal = Calculation::getItem(1);
    auto retVal = Calculation::getItem(1024 * 128 - 1);
    if (retVal.has_value()) {
        std::printf("%d\n", std::any_cast<int>(retVal.value()));
    }
    return 0;
}

and when I run it via CLion, obtained log is:

...
43776
43775
43774
43773
43772
43771
43770
43769

Process finished with exit code 11

avoid stack over flow c++

1 Answers1