Why does my recursive function stack overflow on large inputs?

[Mark.T]

I keep getting a "stack overflow" error in my recursive function, but I can't figure out why the base case isn't being hit. It works fine with small datasets, but it crashes every time with larger input.

[AriaT]

Yeah I know that feeling. In my case the base case looked fine on paper, but one branch never reduced the problem size. I added a depth counter and printed it, and I saw the depth kept growing on some inputs. The culprit was an off by one in the decrement, so n stayed the same on that path and the base case never triggered. Fixing that made large inputs stop blowing the stack.

[StevenW]

That time I realized one branch didn't shrink the input at all; I was recursing on the same n again under a condition that almost never excluded. It looked like progress but it wasn’t. Once I forced every path to pass a smaller n or a smaller subarray, the stack stopped exploding.

[RobertQM]

Another angle is that for big inputs the depth is simply too big. If you can recast it as an iterative loop or a divide-and-conquer that halves the size, you get more predictable memory. I kept the same logic for a while, but eventually changed to a loop with a stack data structure, and the crashes disappeared on big data.

[BrianXG]

Are you sure every path actually reduces the problem? Could a branch call with the same inputs again, so you never hit the base case?