Стек в рекурсии
В C++ стек рекурсии ограничен лишь вашей оперативной памятью.
Пример задачи на рекурсию, которую теоретически можно переписать под стек - это Ханойские башни.
Условие.
У вас есть три стержня (= стека), на первом находятся $N$ дисков, причем чем диск ниже, тем он шире. Можно переносить верхний диска одного стержня на верх другого стержня, если только под ним не будет находиться меньший по ширине диск. Нужно вывести последовательность операций, после которой все диски перенесутся на третий стержень.
Решение.
Достаточно делать как в динамическом программировании - формализовать задачу и свести ее к предыдущим. Давайте функция hanoi(n, from, to, middle) будет выводить все операции с переносом $n$ стержней с верха стержня $from$ на стержень $to$, при условии, что их можно еще пользоваться стержнем $middle$ (и при этом на стержнях $to$ и $middle$ все диски шире, чем эти $n$, чтобы их можно было класть сверху). Тогда на самом деле эта операция разбивается на такие:
- hanoi(n - 1, from, middle, to) - перенести $n-1$ диск на средний стержень
- print(from + " -> " + to) - перенести самый широкий диск на финальный стержень
- hanoi(n - 1, middle, to, from) - перенести $n-1$ диск со среднего стержаня на финальный
Алгоритм работает за $O(2^n)$, так как вызывает два таких же алгоритма для $n-1$.