Программирование без рекурсии

Многие рекомендации по программированию надёжных систем, в частности MISRA C, запрещают использование прямой или косвенной рекурсии из-за плохой предсказуемости этого подхода. В принципе, это разумно, учитывая «железячную» область применения таких рекомендаций — в ней практически нет потребности в рекурсивных алгоритмах, а эквивалентные циклические алгоритмы в императивных языках всегда будут выигрывать. Но что будет, если попытаться применить это жёсткое требование к универсальным применениям? Возможно ли нормальное программирование без рекурсии?

Естественно, меня интересуют алгоритмы рекурсивные по своей природе, так как для нерекурсивных ответ очевиден. Такие алгоритмы при запрете рекурсивных вызовов потребуют использования явной реализации рекурсии вместо встроенной.

Для примера я возьму задачу разбора простейших выражений по методу рекурсивного спуска. Пример хорош тем, что показывает вариант косвенной рекурсии — более сложный для реализации, чем прямой. Для начала напишу простой вариант, а затем изменю программу, отказавшись от рекурсивных вызовов.

Напишем грамматику исходного языка выражений на РБНФ:

expr = adder { ('+' | '-') adder }. 
adder = mult { ('*' | '/') mult }.
mult = number | '(' expr ')'.
number = digit { digit }.
digit = '0' .. '9'.

Для реализации я выбрал язык Go. Такой код у меня получился при использовании рекурсии:

type (
   scanner struct {
      r io.Reader
      buf [4096] byte
      i, len int
  
      l rune
   }
)

func read(s *scanner) error {
   var e error
   s.len, e = s.r.Read(s.buf[:])
   for e == nil && s.len <= 0 {
      s.len, e = s.r.Read(s.buf[:])
   }
   return e
}

func scan(s *scanner) {
   for s.i >= s.len && read(s) == nil {
      s.i = 0
      for s.buf[s.i] == ' ' {
         s.i++
      }
   }
   s.l = rune(s.buf[s.i])
   s.i++
}

func number(s *scanner) int {
   var v int
   if s.l < '0' || s.l > '9' {
      s.l = -1
      v = 0
   } else {
      for s.l >= '0' && s.l <= '9' {
         v = v * 10 + int(s.l - '0') 
         scan(s)
      }
   }
   return v
}

func mult(s *scanner) int {
   var v int
   if s.l == '(' {
      scan(s)
      v = expr(s)
      if s.l == ')' {
         scan(s)
      } else {
         s.l = -1
      }
   } else {
      v = number(s)
   }
   return v
}

func adder(s *scanner) int {
   v := mult(s)
   for s.l == '*' || s.l == '/' {
      if s.l == '*' {
         scan(s)
         v *= mult(s)
      } else  if s.l == '/' {
         scan(s)
         v /= mult(s)
      }
   }
   return v
}

func expr(s *scanner) int {
   v := adder(s)
   for s.l == '+' || s.l == '-' {
      if s.l == '+' { 
         scan(s)
         v += adder(s)
      } else {
         scan(s)
         v -= adder(s)
      }
   }
   return v
}

А такой код получился при явных манипуляциях с пользовательским стеком:

type (
   scanner struct {
      ... /* пропустим совпадающие с исходной версией части*/
   }
   stack struct {
      s [64] struct {
         function, state int
   
         v int
      }
      i int
   }
)

const (
   fExpr = iota
   fAdder
   fMult
)

func read(s *scanner) error {...}
func scan(s *scanner) {...}

func step(st *stack) {
   st.s[st.i].state++
}

func state(st *stack) int {
   return st.s[st.i].state
}

func call(st *stack, fun int) {
   step(st)
   st.i++
   st.s[st.i].function = fun
   st.s[st.i].state = 0
}

func ret(st *stack) {
   st.i--;
}

func jump(st *stack, state int) {
   st.s[st.i].state = state
}

func getret(st *stack) int {
   step(st)
   return st.s[st.i + 1].v
}

func number(s *scanner) int {...}

func mult(st *stack, s *scanner) {
   switch state(st) {
   case 0:
      if s.l == '(' {
         scan(s)
         call(st, fExpr)
      } else {
         st.s[st.i].v = number(s)
         ret(st)
      }
   case 1:
      if s.l == ')' {
         scan(s)
         st.s[st.i].v = getret(st)
         ret(st)
      } else {
         s.l = -1
         ret(st)
      }
   }
}

func adder(st *stack, s *scanner) {
   switch state(st) {
   case 0:
      call(st, fMult)
   case 1:
      st.s[st.i].v = getret(st)
      jump(st, 5)
   case 2:
      if s.l == '/' {
         step(st)
      }
      scan(s)
      call(st, fMult)
   case 3:
      st.s[st.i].v *= getret(st)
      step(st)
   case 4:
      st.s[st.i].v /= getret(st)
   case 5:
      if s.l == '*' || s.l == '/' {
         jump(st, 2)
      } else {
         ret(st)
      }
   }
}

func expr(st *stack, s *scanner) {
   switch state(st) {
   case 0:
      call(st, fAdder)
   case 1:
      st.s[st.i].v = getret(st)
      jump(st, 5)
   case 2:
      if s.l == '-' {
         step(st)
      }
      scan(s)
      call(st, fAdder)
   case 3:
      st.s[st.i].v += getret(st)
      step(st)
   case 4:
      st.s[st.i].v -= getret(st)
   case 5:
      if s.l == '+' || s.l == '-' {
         jump(st, 2)
      } else {
         ret(st)
      }
   } 
}

func calc(s *scanner) int {
   var st stack
   st.i = 0
   st.s[0].function = fExpr
   for st.i >= 0 {
      switch st.s[st.i].function {
      case fExpr:
         expr(&st, s)
      case fAdder:
         adder(&st, s)
      case fMult:
         mult(&st, s)
      }
   }
   return st.s[0].v
}

Общий размер программы увеличился практически вдвое. К тому же, для функций, пролегающих через косвенную рекурсию (expr->adder->mult->expr) пришлось фактически отказаться от структурных управляющих конструкций, перейдя к переходам по меткам, что прекрасно эмулируется с помощью switch. Это понадобилось для вызова рекурсивных псевдофункций: fExpr, fAdder, fMult.

Мне кажется нерациональным запрет в общем случае на такую простую вещь, как рекурсия без предоставления адекватной замены. Такой заменой может стать разновидность функций, которые могут приостанавливать своё выполнение с возможностью возобновления при следующем обращении. Эти функции привлектельны и тем, что способны упростить использование кооперативной многозадачности, что может быть востребовано в микроконтроллерах, но полноценная реализация такой возможности куда сложней, чем обыкновенная рекурсия.

Полный исходный код примеров доступен на github.