I've been solving some challenges at codesignal.com using C-Lisp to learn it and I've been avoiding using loops to make lisp style code.
In this challenge called alternatingSums (which gives you an int array a that can be very large and ask you to return an array/list {sumOfEvenIndexedElements, sumOfOddIndexedElements}) i have been receiving stack overflow error with this code:
(defun alternatingSums(a &optional (index 0) (accumulated '(0 0)))
(cond ((= index (length a))
accumulated)
((evenp index)
(alternatingSums
a
(1+ index)
`(,(+ (svref a index ) (elt accumulated 0)) ,(elt accumulated 1)))
)
((oddp index)
(alternatingSums
a
(1+ index)
`(,(elt accumulated 0) ,(+ (svref a index ) (elt accumulated 1))))
)
)
)
isn't it tail-recursive or can tail-recursive functions still get stack-overflow?
Recursive functions which call themselves from tail position can lead to stack overflow; language implementations must support some form of tail call elimination to avoid the problem.
I've been avoiding using loops to make lisp style code.
Common Lisp does not require that implementations do tail call elimination, but Scheme implementations must do so. It is idiomatic in Scheme to use recursion for iteration, but in Common Lisp it is idiomatic to use other iteration devices unless recursion provides a natural solution for the problem at hand.
Although Common Lisp implementations are not required to do tail call elimination, many do. Clisp does support limited tail call elimination, but only in compiled code, and only for self-recursive tail calls. This is not well-documented, but there is some discussion to be found here @Renzo. OP posted code will be subject to tail call elimination when compiled in Clisp since the function alternatingSums calls itself from tail position. This covers most cases in which you may be interested in tail call elimination, but note that tail call elimination is then not done for mutually recursive function definitions in Clisp. See the end of this answer for an example.
Defining a function from the REPL, or loading a definition from a source file, will result in interpreted code. If you are working in a development environment like SLIME, it is easy to compile: from the source file buffer either do Ctrl-c Ctrl-k to compile the whole file and send it to the REPL, or place the point inside of or immediately after a function definition and do Ctrl-c Ctrl-c to compile a single definition and send it to the REPL.
You could also compile the source file before loading it, e.g. (load (compile-file "my-file.lisp")). Or you could load the source file, and compile a function after that, e.g. (load "my-file.lisp"), then (compile 'my-function).
As already mentioned, it would probably be more likely that idiomatic Common Lisp code would not use recursion for this sort of function anyway. Here is a definition using the loop macro that some would find more clear and concise:
(defun alternating-sums (xs)
(loop for x across xs
and i below (length xs)
if (evenp i) sum x into evens
else sum x into odds
finally (return (list evens odds))))
Here is a simple pair of mutually recursive function definitions:
(defun my-evenp (n)
(cond ((zerop n) t)
((= 1 n) nil)
(t (my-oddp (- n 1)))))
(defun my-oddp (n)
(my-evenp (- n 1)))
Neither function calls itself directly, but my-evenp has a call to my-oddp in tail position, and my-oddp has a call to my-evenp in tail position. One would like for these tail calls to be eliminated to avoid blowing the stack for large inputs, but Clisp does not do this. Here is the disassembly:
CL-USER> (disassemble 'my-evenp)
Disassembly of function MY-EVENP
14 byte-code instructions:
0 (LOAD&PUSH 1)
1 (CALLS2&JMPIF 172 L16) ; ZEROP
4 (CONST&PUSH 0) ; 1
5 (LOAD&PUSH 2)
6 (CALLSR&JMPIF 1 47 L19) ; =
10 (LOAD&DEC&PUSH 1)
12 (CALL1 1) ; MY-ODDP
14 (SKIP&RET 2)
16 L16
16 (T)
17 (SKIP&RET 2)
19 L19
19 (NIL)
20 (SKIP&RET 2)
CL-USER> (disassemble 'my-oddp)
Disassembly of function MY-ODDP
3 byte-code instructions:
0 (LOAD&DEC&PUSH 1)
2 (CALL1 0) ; MY-EVENP
4 (SKIP&RET 2)
Compare with a tail recursive function that calls itself. Here there is no call to factorial in the disassembly, but instead a jump instruction has been inserted: (JMPTAIL 2 5 L0).
(defun factorial (n acc)
(if (zerop n) acc
(factorial (- n 1) (* n acc))))
CL-USER> (disassemble 'factorial)
Disassembly of function FACTORIAL
11 byte-code instructions:
0 L0
0 (LOAD&PUSH 2)
1 (CALLS2&JMPIF 172 L15) ; ZEROP
4 (LOAD&DEC&PUSH 2)
6 (LOAD&PUSH 3)
7 (LOAD&PUSH 3)
8 (CALLSR&PUSH 2 57) ; *
11 (JMPTAIL 2 5 L0)
15 L15
15 (LOAD 1)
16 (SKIP&RET 3)
Some Common Lisp implementations do support tail call elimination for mutually recursive functions. Here is the disassembly of my-oddp from SBCL:
;; SBCL
; disassembly for MY-ODDP
; Size: 40 bytes. Origin: #x52C8F9E4 ; MY-ODDP
; 9E4: 498B4510 MOV RAX, [R13+16] ; thread.binding-stack-pointer
; 9E8: 488945F8 MOV [RBP-8], RAX
; 9EC: BF02000000 MOV EDI, 2
; 9F1: 488BD3 MOV RDX, RBX
; 9F4: E8771B37FF CALL #x52001570 ; GENERIC--
; 9F9: 488B5DF0 MOV RBX, [RBP-16]
; 9FD: B902000000 MOV ECX, 2
; A02: FF7508 PUSH QWORD PTR [RBP+8]
; A05: E9D89977FD JMP #x504093E2 ; #<FDEFN MY-EVENP>
; A0A: CC10 INT3 16 ; Invalid argument count trap
This is a little harder to read than the previous examples because SBCL compiles to assembly language instead of byte code, but you can see that a jump instruction has been substituted for the call to my-evenp:
; A05: E9D89977FD JMP #x504093E2 ; #<FDEFN MY-EVENP>