Многие рекомендации по программированию надёжных систем, в частности MISRA C, запрещают использование прямой или косвенной рекурсии из-за плохой предсказуемости этого подхода. В принципе, это разумно, учитывая «железячную» область применения таких рекомендаций — в ней практически нет потребности в рекурсивных алгоритмах, а эквивалентные циклические алгоритмы в императивных языках всегда будут выигрывать. Но что будет, если попытаться применить это жёсткое требование к универсальным применениям? Возможно ли нормальное программирование без рекурсии?
Естественно, меня интересуют алгоритмы рекурсивные по своей природе, так как для нерекурсивных ответ очевиден. Такие алгоритмы при запрете рекурсивных вызовов потребуют использования явной реализации рекурсии вместо встроенной.
Для примера я возьму задачу разбора простейших выражений по методу рекурсивного спуска. Пример хорош тем, что показывает вариант косвенной рекурсии — более сложный для реализации, чем прямой. Для начала напишу простой вариант, а затем изменю программу, отказавшись от рекурсивных вызовов.
Напишем грамматику исходного языка выражений на РБНФ:
expr = adder { ('+' | '-') adder }.
adder = mult { ('*' | '/') mult }.
mult = number | '(' expr ')'.
number = digit { digit }.
digit = '0' .. '9'.
Для реализации я выбрал язык Go. Такой код у меня получился при использовании рекурсии:
