Recursion in lambda in Elisp

Question

I have the following Python code:

def sum_fibonacci():
    '''Project Euler: 2
    Sum of even-valued terms of Fibonacci sequence < 4 mil
    '''
    def i(a, b, acc):
        if a >= 4000000: return acc
        if a % 2 == 0:
            return i(a + b, a, acc + a)
        else: return i(a + b, a, acc)
    return i(2, 1, 0)

I want to translate it to Emacs Lisp. In Higher-order functions in Elisp i was told not to use defun within defun, because it enables the function globally, so i wrote lambda instead. But i need to make lambda call itself recursively.

My code is:

(defun sum-fibonacci ()
  (let ((i
         (lambda (a b acc)
           (cond ((>= a 4000000) acc)
                 ((evenp a) (funcall i (+ a b) a (+ a acc)))
                 (t (funcall i (+ a b) a acc))))))
    (funcall i 2 1 0)))

However the function i is called before it is assigned with let, and i get an error - *** Eval error *** Symbol's value as variable is void: i

How do i do recursion in lambda in Elisp?

You might also want to discover `flet`. – tripleee Nov 15 '12 at 10:03 — tripleee, Nov 15 '12 at 10:03

score 6 · Answer 1 · answered Nov 13 '12 at 13:43

Yes you can do this in emacs lisp.

(funcall (lambda (fib a b acc) (funcall fib a b acc fib)) ;;lambda1
         (lambda (a b acc fib)                            ;;lambda2
           (cond ((>= a 40000) acc)
                 ((zerop (mod a 2)) (funcall fib (+ a b) a (+ acc a) fib))
                 (t (funcall fib (+ a b) a acc fib))))
         2 1 0)

The main idea is using a helper lambda (lambda1) to call the real lambda (lambda2) and pass the real lambda (lambda2) to itself.

score 4 · Accepted Answer · edited May 23 '17 at 12:31

4

Per Recursing in a lambda function I rewrote it with labels:

(defun sum-fibonacci ()
  (labels ((i (a b acc)
              (cond ((>= a 4000000) acc)
                    ((evenp a) (i (+ a b) a (+ a acc)))
                    (t (i (+ a b) a acc)))))
    (i 2 1 0)))

edited May 23 '17 at 12:31

Community

1
1

answered Nov 13 '12 at 07:53

Mirzhan Irkegulov

17,660
12
105
166

score 2 · Answer 3 · answered Nov 13 '12 at 07:34

Just remove the commas in the lambda list:

(defun sum-fibonacci ()
  (labels ((rec (a b acc)
                (cond ((>= a 4000000) acc)
                      ((evenp a) (rec (+ a b) a (+ a acc)))
                      (t (rec (+ a b) a acc)))))
    (rec 2 1 0)))

Recursion in lambda in Elisp

3 Answers3