Simple Recursion

A recursive procedure is a procedure which applies itself. In C# recursion is possible, but generally iteration is the preferred idiom. Scheme is a languages designed to be good at recursion, and since it doesn't have iteration it is in fact the only way.

In Scheme you can learn a lot about recursion, using a tiny subset of the language; an approach exemplified by the Little Schemer. The basic bits you need are:

Command	What it does
(quote x)	returns x, normally (quote x) is abbreviated to 'x.
(car l)	returns the first element of a list, l.
(cdr l)	returns the list l, except for it's first element.
(cons e l)	pushes e onto the front of the list, l.
(cond (p1 e1)....(pn en))	Conditional expression. The p expressions are evaluated in order until one of them returns true. When one is found the corresponding e expression is returned.
(null? l)	returns true (#t) if the list l is empty, false (#f) otherwise.
(eq? a b)	returns true (#t) if a and b are equal, false (#f) otherwise.

Most recursive procedures should have at least two basic elements, a base case and a recursion step. Consider these examples:

The procedure member? takes 2 arguments, a symbol, e, and a list, lst. It returns true if e is in the list, otherwise returns false.


(define member?
  (lambda(e lst)
    (cond
      ((null? lst) #f)
      ((eq? e (car lst)) #t)
      (else (member? e (cdr lst))))))

The procedure insert-right takes 3 arguments, new, old and lst. It inserts new into lst to the right of the first occurance of old.


(define insert-right
  (lambda (new old lst)
    (cond
      ((null? lst) '())
      ((eq? old (car lst)) (cons old (cons new (cdr lst))))
      (else (cons (car lst) (insert-right new old (cdr lst)))))))

The procedure any? takes a list of booleans as an argument. It returns true if any are true, otherwise returns false.


(define any?
  (lambda (lst)
    (cond
      ((null? lst) #f)
      ((car lst) #t)
      (else (any? (cdr lst))))))

The procedure reject takes two arguments a predicate test? and a list lst. It returns a new list of items which fail test?


(define reject
  (lambda (test? lst)
    (cond
      ((null? lst) '())
      ((test? (car lst)) (reject test? (cdr lst)))
      (else (cons (car lst) (reject test? (cdr lst)))))))

The Little Schemer summarises it's rules for writing recursive procedures as commandments:

First Commandment - When recurring on a list, lst, ask two questions about it: (null? lst) and else.
Second Commandment - Use cons to build lists.
Third Commandment - When building a list, describe the first typical element, and then cons it on to the natural recursion.
Fourth Commandment - Always change at least one argument while recurring. When recurring on a list, lst, use (cdr lst). It must be changed closer to termination. The changing argument must be tested in the termination condition. When using cdr test termination with null?

You can download the code with tests here.