I am learning Lisp from the book "The Land of Lisp" by Conrad Barski. Now I have hit my first stumbling block, where the author says:
Calling yourself in this way is not only allowed in Lisp, but is often strongly encouraged
after showing the following example function to count the items in a list:
(defun my-length (list)
(if list
(1+ (my-length (cdr list)))
0))
When I call this function my-length with a list containing a million items, I get a stack overflow error. So either you never expect to have a list that long in Lisp (so maybe my use case is useless) or there is another way to count items in such a long list. Can you maybe shine some light on this? (I am using GNU CLISP on Windows, by the way).
Creating recursive functions to operate on recursive datastructures is indeed good for in lisp. And a list (in lisp) is defined as a recursive datastructure, so you should be ok.
However, as you have experienced, if traversing a datastructure a million items deep using recursion, will also allocate a million frames on the stack, and you can expect a stack overflow unless you specifically ask your runtime environment to allocate huge amount of stack-space (I have no idea if or how you could do this in gnu clisp...).
First of all, I think this shows that the list-datastructure isn't really a the best for everything, and in this case another structure might be better (however, you might not have come to vectors in your lisp-book yet ;-)
Another thing is that for large recursions such as this to be effective, the compiler should optimise tail recursions and convert them into iterations. I don't know if clisp has this functionality, but you would need to change your function to actually be optimisable. (If "tail recursion optimisation" makes no sense, please let me know and I can dig up some references)
For other ways of iterating, take a look at:
Or other datastructures: