﻿ Simple Recursion

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

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?