Через скобочки к ЛИСПу: неудавшееся домашнее задание для Coursera.org
Feb 08, 2013 11:00
Недавно стартанул кур Algorithms: Design & Analysis (Part I). Так как параллельно с ним я изучаю LISP (sbcl), то решено было задания писать на нем. В результате по первой неделе был написан следующий код:[Spoiler (click to open)] (defvar *inv* 0) (defun count-inversions (input) (if (> (length input) 1) (let ((length-input (floor (/ (length input) 2)))) (count-and-merge (count-inversion subseq input 0 length-input) (count-inversion subseq input length-input)))) input))
Все здорово работаетна небольших файлах, но как только появляется 100.000 курсеровского задания выходит за стек.
Т.е. древний и до мозга костей функциональный ЛИСП не умеет рекурсию оптимизировать (я вижу, что рекурия не хвостовая)? Или я что-то делаю очень не так?