# 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:

 (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?