0

I have been working on implementing a priority queue of strings in c++ using a binary tree.

As I think the simplicity of recursion is great. I am not going to post code as I have already spent a long time today with the debugger and I am not asking for someone to debug for me, but basically after implementing recursive methods to dequeue and insert elements and testing correct behavior with up to 1000 random strings I have used a test hub that tries to enqueue 10000 random strings and I have a stack overflow error. After this, I have changed my recursive methods for others that use a pointer cursor to scan my tree to insert and dequeue using the same logic and it has not crashed as I expected (i have coded it almost as a linked list).

The question is then, Can I cause stack overflow through recursion even if I use to pass by reference?

These recursive methods are part of a class and defined as private.

I hope the question is not vague but I am still not experienced enough in c++. Thanks a lot for your help!

nhouser9
  • 6,730
  • 3
  • 21
  • 42
Lumbreras
  • 36
  • 7
  • Possible duplicate of [Stack overflow exception with recursion](http://stackoverflow.com/questions/33766776/stack-overflow-exception-with-recursion) – Prune Jul 18 '16 at 23:13
  • Possible duplicate of [What is a StackOverflowError?](http://stackoverflow.com/questions/214741/what-is-a-stackoverflowerror) – nhouser9 Jul 19 '16 at 06:18

1 Answers1

1

In recursion you're calling your function again and again. On every call you use the stack memory for parameters, stack variables and more. So basicly the answer is definitely yes, a deep recursion can cause a stack overflow.

Ohad Eytan
  • 8,114
  • 1
  • 22
  • 31
  • 1
    And an infinite recursion is guaranteed to cause the error. – PM 77-1 Jul 18 '16 at 23:00
  • @PM77-1 on a finite machine :) – Ohad Eytan Jul 18 '16 at 23:02
  • We only have finite machines in this state – D Hydar Jul 19 '16 at 01:07
  • I did consider errors in my code but the insert function I built is literally equivalent to the one found here: http://www.cprogramming.com/tutorial/lesson18.html – Lumbreras Jul 20 '16 at 10:31
  • @Lumbreras nobody says that you code is wrong. Even correct code of recursion will cause stack overflow if the recursion is too deep. Perhaps you should consider another approach to your task. – Ohad Eytan Jul 20 '16 at 10:35
  • @OhadEytan sorry I did not mean to sound defensive! I made it work with 10000 strings via the use of a pointer cursor that runs along the tree but I am just very curious about this, I found that: > Calling recursively and passing by value my code crashes after en queuing just over 1500 strings. > Calling recursively but passing by reference it goes all the way to inserting up to 3800 strings. > Using the pointer cursor it happily takes on all the 10000 strings Is this making sense? Thanks a lot to all for your comments and help to understand recursion better! – Lumbreras Jul 20 '16 at 21:37
  • @Lumbreras You`re welcome. I think it does make sense and that's a good way to investigate and learn things. Good luck – Ohad Eytan Jul 20 '16 at 21:49