Ищете пример, чтобы наглядно проиллюстрировать, что хвостовые рекурсивные вызовы занимают меньше места, чем не хвостовые рекурсивные?

Разработчикам программного обеспечения на языках функционального программирования сказали, что хвостовые рекурсивные вызовы лучше, чем не хвостовые. Классическим примером в учебниках является хвостовая рекурсивная факториальная функция (написанная на F#).

let rec faci n r = 
  if n = 0 then r else faci (n-1) (r * n) 

по сравнению с его не-рекурсивным аналогом.

let rec facr n = 
  if n = 0 then 1 else n * facr(n-1)

Относительно ясно, что faci выше не требует дополнительного кадра стека при вызове себя как facrсделал бы. Но я ищу более яркий пример, предпочтительно на F#, из которого можно продемонстрировать, почему хвостовые рекурсивные функции лучше, чем нехвостовые. В идеале улучшение можно визуализировать, например, с помощью профилировщика памяти или распечатав некоторую отладочную информацию. Есть идеи о таком примере?

0 ответов

Другие вопросы по тегам