Должны ли мы рассматривать рекурсивный стек вызовов как вспомогательное пространство?
Должны ли мы рассматривать рекурсивный стек вызовов как вспомогательное пространство, используемое программой? Я думаю, что это следует учитывать только при расчете сложности пространства, но не при расчете вспомогательного пространства.
Вспомогательное пространство — это дополнительное пространство или временное пространство, используемое алгоритмом. Пространство Сложность алгоритма — это общее пространство, занимаемое алгоритмом по отношению к входному размеру.
Решение
Если вы на самом деле полагаетесь на переменные во внешних вызовах — если они понадобятся вам снова после возврата самого внутреннего вызова — тогда да, они должны быть включены во вспомогательное пространство.
Но если все, что у вас есть хвостовые вызовы, и единственная причина, по которой ваш стек растет, заключается в том, что ваш компилятор не поддерживает оптимизацию хвостовых вызовов, тогда я не думаю, что рассмотрел бы это во вспомогательном пространстве (абстрактно) алгоритм, хотя ваш фактический реализация в конечном итоге займет это место.
Другие решения
Других решений пока нет …