Рекурсия против ручных стеков. Что предпочтительнее в каком случае?

Question

Рекурсивная программа внутренне создает стек и заставляет пользователей писать меньше кода.

Есть ли случаи, когда рекурсия на самом деле предпочтительнее ручных стеков по причине, отличной от упомянутой выше?

РЕДАКТИРОВАТЬ 1:

Каким образом динамическое выделение памяти является более "дорогим", чем выделение в куче рекурсивной программой?

Answer 1

Основная причина, на которую, я думаю, вы ссылаетесь, когда говорите «меньше кода», это ясность и простота дизайна. На языке с такими функциями, как локальные переменные и автоматическое хранение, использовать эти функции бесконечно более естественно, чем структурировать все в домашние стеки. (В конце концов, зачем вообще использовать функции? Почему бы не написать всю программу, используя if / else и while в качестве единственных управляющих структур?)

Еще одним фактором является производительность, особенно в многопоточных средах. Рекурсия & mdash; в зависимости от языка & mdash; скорее всего будет использовать стек (обратите внимание: вы говорите "создает стек внутри", но на самом деле он использует стек, который программирует на таких языках всегда ), тогда как ручной стек структура потребует динамического выделения памяти , что часто приводит к заметному снижению производительности & mdash; не говоря уже о дополнительной сложности обеспечения освобождения всей этой памяти, когда вы, скажем, встречаете исключение.

Answer 2

Я в основном согласен с ответом @ ruakh. Я бы только добавил, что использование системного стека имеет много накладных расходов (на самом деле вы выдвигаете намного больше состояний, чем нужно каждый раз, когда выполняете рекурсию) и может вызвать переполнение стека для очень глубокой (но ограниченной) рекурсии, что вы, возможно, сможете чтобы избежать, используя явный стек и выдвигая только необходимое вам состояние.

Answer 3

ВНЕШНЕЕ ИСПОЛЬЗОВАНИЕ ЗАПАСОВ

vector<int> Solution::inorderTraversal(TreeNode* A) {
vector<int> res;
stack<TreeNode* > st;
TreeNode* root=A;
while(true)
{
    if(root==NULL)
    {
        if(st.empty())
        break;
        root=st.top();
        st.pop();
        res.push_back(root->val);
        root=root->right;


    }
    else
    {

        st.push(root);
        root=root->left;
    }
}
return res;

}

ИСПОЛЬЗОВАНИЕ РЕКУРСИИ

void inorder(struct node* root)

но здесь мы видим, что внешнее использование стеков экономит много времени на обработку, и, следовательно, подход со стеками быстрее.