Proper use of tail recursion while forming a list As a project to better develop my understanding of functional programming, I am writing a prime number generator in Scheme. I am using a simple brute-force algorithm to detect whether a number is prime and I know there are better algorithms. What I'm interested is whether my attempt at the brute-force algorithm can be better written and whether I am using tail recursion appropriately and forming the list efficiently. The goal is to have a list of numbers at the end I can use for some task or print out. Maybe even write it as a generator where I can continually ask it for the next prime. Here is my current code:

(define is_prime1
 (lambda(num div)
  (if (= num div)
   #t
   (if (= (remainder num div) 0)
    #f
    (is_prime1 num (+ div 1))
   )
  )
 )
)

(define is_prime
 (lambda(num)
  (if (&lt; num 2) #f (is_prime1 num 2))
 )
)

(define list_primes1
 (lambda(idx num)
  (if (&lt;= idx num)
   (if (not (is_prime idx))
    (list_primes1 (+ idx 1) num)
    (cons idx
     (list_primes1 (+ idx 1) num)
    )
   )
   '()
  )
 )
)

(define list_primes
 (lambda(num)
  (list_primes1 0 num)
 )
)

(define print_primes
 (lambda(primes)
  (if (null? primes)
   '()
   (list
    (display (car primes))
    (newline)
    (print_primes (cdr primes))
   )
  )
 )
)

(print_primes (list_primes 4095))
Your algorithm is okay, but the real issue with this code is that your code style is atrocious, bordering on unreadable. Your style exhibits four main problems:


Scheme is not C, and parentheses are not curly braces. Do not put close parens on separate lines. Scheme code is intended to be read primarily by observing indentation, which brings me to the next point.
Your indentation is wrong. Again, Scheme is not C, and expressions should be indented to align subexpressions, not with a consistent 1-, 2- or 4-space indent. For an explanation of why this is so important, see this Stack Overflow answer.
This is a less significant point, but your explicit use of lambda here is unnecessary. There is a shorthand form with define that is equivalent to define paired with lambda, and it’s more idiomatic and easier to visually parse.
Identifiers in Scheme should be hyphenated (lisp-case), not separated by underscores (snake_case).


Just following the above formatting changes, your code becomes much more readable to a Schemer:

(define (is-prime1 num div)
  (if (= num div)
      #t
      (if (= (remainder num div) 0)
          #f
          (is-prime1 num (+ div 1)))))

(define (is-prime num)
  (if (&lt; num 2) #f (is-prime1 num 2)))

(define (list-primes1 idx num)
  (if (&lt;= idx num)
      (if (not (is-prime idx))
          (list-primes1 (+ idx 1) num)
          (cons idx
                (list-primes1 (+ idx 1) num)))
      '()))

(define (list-primes num)
  (list-primes1 0 num))

(define (print-primes primes)
  (if (null? primes)
      '()
      (list (display (car primes))
            (newline)
            (print-primes (cdr primes)))))

(print-primes (list-primes 4095))


Now we can focus on some more substantive code improvements. First of all, print-primes is an easy candidate for elimination. Not only does it needlessly produce a list, it can be trivially implemented using the for-each higher-order function. The name is also silly, since it does not print primes, it prints each element of a list. There is no reason to include the word “primes” in the name.

Instead, just replace the whole function with a simple use of for-each:

(define (displayln x) (display x) (newline))
(for-each displayln (list-primes 4095))


Next, let’s look at the bulk of the code. You have defined list-primes in terms of a helper functions, list-primes1. Since all your list-primes function is doing is calling list-primes1 with some arguments set, you can replace the helper function with a use of “named let”:

(define (list-primes num)
  (let loop ((idx 0)
             (num num))
    (if (&lt;= idx num)
        (if (not (is-prime idx))
            (loop (+ idx 1) num)
            (cons idx
                  (loop (+ idx 1) num)))
        '())))


You also have a pair of nested ifs, which might be more readably  represented with a cond:

(define (list-primes num)
  (let loop ((idx 0)
             (num num))
    (cond
      ((&gt; idx num)
       '())
      ((is-prime idx)
       (cons idx (loop (+ idx 1) num)))
      (else
       (loop (+ idx 1) num)))))


Taking a look at is-prime and is-prime1, we can once again replace is-prime1 with a use of named let:

(define (is-prime num)
  (if (&lt; num 2)
      #f
      (let loop ((num num)
                 (div 2))
        (if (= num div)
            #t
            (if (= (remainder num div) 0)
                #f
                (loop num (+ div 1)))))))


However, this is still much more complicated than it needs to be. Due to how Scheme’s and and or are both short-circuiting and implement “truthiness”, where all non-#f values are truthy, we can replace most of the uses of if with and or or:

(define (is-prime num)
  (and (&gt;= num 2)
       (let loop ((num num)
                  (div 2))
         (or (= num div)
             (and (not (= (remainder num div) 0))
                  (loop num (+ div 1)))))))


Also, we can replace (= x 0) with the zero? predicate to improve readability:

(define (is-prime num)
  (and (&gt;= num 2)
       (let loop ((num num)
                  (div 2))
         (or (= num div)
             (and (not (zero? (remainder num div)))
                  (loop num (+ div 1)))))))


Now, it’s worth noting that list-primes is not tail recursive, since in the second cond case, a call to cons is in tail position, not loop. A way to make this function tail recursive is to build up a list iteratively, then reverse it at the end:

(define (list-primes num)
  (reverse
   (let loop ((idx 0)
              (num num)
              (acc '()))
     (cond
       ((&gt; idx num)
        acc)
       ((is-prime idx)
        (loop (+ idx 1) num (cons idx acc)))
       (else
        (loop (+ idx 1) num acc))))))


This leaves us with the final, completely tail-recursive program:

(define (is-prime num)
  (and (&gt;= num 2)
       (let loop ((num num)
                  (div 2))
         (or (= num div)
             (and (not (zero? (remainder num div)))
                  (loop num (+ div 1)))))))

(define (list-primes num)
  (reverse
   (let loop ((idx 0)
              (num num)
              (acc '()))
     (cond
       ((&gt; idx num)
        acc)
       ((is-prime idx)
        (loop (+ idx 1) num (cons idx acc)))
       (else
        (loop (+ idx 1) num acc))))))

(define (displayln x) (display x) (newline))
(for-each displayln (list-primes 4095))