Как исправить Stack Overflow при рекурсии с использованием std::thread и templates?

Question

[whoami?root root_toor]

Код ниже:

#include <iostream>
#include <algorithm>
#include <locale>
#include <exception>

using namespace std;

double last_pos = 0x00;
int N = 0x00;

void str_cut()
{	++last_pos; // падает на == 3805
	
	if (last_pos > 64*1024) {
		return;			// exit condition
	}
	else {
		try {
			str_cut();	// Move semantics ONLY!
		}
		catch (std::exception const& e) {
			throw exception{};
			cerr << "Stack Overflow detected!" << /*e << */endl;
		}
	}

}

int main()
{
	try {
		// UTF-8 settings here
		setlocale(LC_ALL, "");
		setlocale(LC_ALL, "rus");

		std::cout.flush();
		str_cut();

		system("pause");
		return 0;

	}
	catch (...) {
		// stack overflow exception handling
		throw exception{};
		cerr << "Stack Overflow detected!" << /*e << */endl;
	}

}

Программа падает с Stack Overflow.
Упростил все для наглядности, теперь видно что происходит тупо превышение глубины стека (почему именно около 4000 вызовов?)
*Передачу по значению исправил с помощью move-семантики, утечек больше нет!
Но, как я понимаю, рекурсию придется убирать, хотя бы вот так:
while(last_pos < 65535) str_cut();

И сопутствующие вопросы:
1) Достаточно ли того, что я установил в начале программы локаль для работы с utf-8? (обрабатывать русские символы и т.д.)
2) Как в данном случае правильно обработать исключения?

ЗЫ: Буду рад любым советам!

Answer 1

[Александр Ручкин]

Не вчитывался в алгоритм, но, если верно понимаю, чем меньше N, тем больше глубина рекурсии, оттуда и stack overflow. Дело не во входной последовательности, а в локальных переменных и аргументах функции. Так что меняйте на цикл.

Что касается Access Denied и прочих, скорее всего другие ошибки есть.

Answer 2

[maaGames]

N - количество символов, но не глубина рекурсии. Если есть ошибка в алгоритме, например, он зацикливается, то переполнение стека произойдёт даже если под стек выделить всю память, включая дисковую и с рядом стоящего компьютера тоже.
Создай глобальную переменнную и увеличивай её значение при каждом входе в функцию str_cut и уменьшай значение при выходе (лучше сделай для этих целей класс, чтобы деструктор сам уменьшал значение). В момент падения посмотри значение, оно будет показывать реальную глубину рекурсии.

Типа такого код добавить надо:

int counter = 0;

class Counter
{
public:
   Counter( int & c )
: counter(c)
{
  ++counter;
}
~Counter()
{
  --counter;
}
int & counter;
};


str_cut()
{
  Counter _(counter);
}

Comments

[whoami?root root_toor]

спасибо за совет! странно только что программа падает уже при возврате из рекурсивных функций..

[maaGames]

whoami?root root_toor: Не сдержался и сам собрал. При N=10 падает на глубине рекурсии 2659. Так же ты передаёшь string по значению, а не по ссылке, т.е. в момент падения существует 2659 копий исходной строки. С алгоритмом не разбирался, но либо в нём ошибка, либо переполнение стека идёт за счёт аргументов функции и адресов возврата.
По идее, в алгоритме ошибка. У тебя там довольно короткие слова, так что N должно быть больше любого максимально длинного слова, чтобы вообще перестать влиять на алгоритм. Слов по 10-40 и больше символов нету в этой строке, так что не понятно, как N влияет. Ищи косяк.

[whoami?root root_toor]

Еще раз спасибо, maaGames! пока не было времени посмотреть основательно, но сейчас склоняюсь к тому что ошибка в передаче аргументов (2659 копий строки это как раз примерно 64 Кб данных поделенных на длину строки, или около того ...), хотя возможно и с алгоритмом косяк, буду думать)

[whoami?root root_toor]

немного начинаю понимать причину падения программы: жуткие утечки памяти!
Должно храниться всего 64 Кб данных (входная последовательность создающаяся в отдельном потоке), а по факту хранится 192 Мб данных! Т.е. при каждом рекурсивном вызове выделяется память по 64 Кб, как раз 64 Кб * 2900 вызовов примерно сходится ...
Пока не понял почему поток выделяет данные на каждый вызов (он вроде бы обособлен от рекурсии) но теперь понятно почему стек переполняется) буду думать дальше, но по прежнему буду рад советам!

[maaGames]

whoami?root root_toor: Для начала передавай строки по ссылке, а не по значению. И у меня есть подозрение, что зря с конца ищешь.
Эту задачу нужно решать не рекурсивно, но ты, видимо, в рекурсии практикуешься... Попробуй уменьшить строку до десятка слов и в отладчике пройтись по алгоритму по шагам, изучая вывод в консоль и прочее.

[whoami?root root_toor]

вроде разобрался, изменил свой первый пост ... все таки придется обойтись без рекурсии)