To evaluate an application:
  Evaluate the operator to get the procedure.
  Evaluate the operands to get the arguments.
  Apply the procedure to the arguments.
    Copy the body of the procedure,
      substituting the arguments supplied for the
      formal parameters of the procedure.
    Evaluate the resulting new body.

Below is a trace of the substitution rule in action.

Sum of squares:

(define (sos x y)
  (+ (sq x) (sq y)))
(define (sq x)
  (* x x))

Trace of sum of squares:

(sos 3 4)
(+ (sq 3) (sq 4))
(+ (sq 3) (* 4 4))
(+ (sq 3) 16)
(+ (* 3 3) 16)
(+ 9 16)
25

For now take + and * to be primitive, as we need to ignore details. The key to understanding complicated things is knowing what not to look at, what not to compute, what not to think about.

An if statement comprises a predicate, consequent and alternative. Learn the names of what we're handling. Once you have the name of a spirit, you have power over it.

(if <predicate>
    <consequent>
    <alternative>)

Evaluation of an if expression:

 To evaluate an if expression:
  Evaluate the predicate expression.
    If it yields true,
      evaluate the consequent expression.
    Otherwise,
      evaluate the alternative expression.

Below are two possible ways of implementing addition of positive integers.

(define (+ x y)
  (if (= x 0)
      x
      (+ (-1+ x) (1+ y))))
(define (+ x y)
  (if (= x 0)
      x
      (1+ (+ (-1+ x) y))))

What do their traces look like?

(+ 3 4)
(+ 2 5)
(+ 1 6)
(+ 0 7)
7

(+ 3 4)
(1+ (+ 2 4))
(1+ (1+ (+ 1 4)))
(1+ (1+ (1+ (+ 0 4))))
(1+ (1+ (1+ 4)))
(1+ (1+ 5))
(1+ 6)
7

The first is an iteration, because: $$time\; =\; O(x),\; space\; =\; O(1)$$

The second is a linear recursion, because: $$time\; =\; O(x),\; space\; =\; O(x)$$

Evidently, the first is better.

Another example of a recursive procedure, is the procedure to draw a circle.

(define (circle x y)
  (plot x y)
  (circle (- x (* y dt))
          (+ y (* x dt))))

Below is a rudimentary procedure for calculating the nth Fibonacci number (i.e. the number of rabbits in the nth generation).

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1))
         (fib (- n 2))))))

The trace produces the below tree.

            fib4
          /      \
         /        \
       fib3       fib2
       /  \        / \
      /    \      /   \
    fib2  fib1  fib1  fib0
    / \     |    |      |
   /   \    1    1      0
 fib1  fib0
​  |      |
  1      0

$$time\; =\; O(fib(n)),\; space\; =\; O(n)$$

There are better algorithms for calculating the nth Fibonacci number. In the above example, fib2 is calculated twice (one of the calculations is redundant). By visualising algorithms, it is easier to determine where improvements can be made.

Construct recursive procedures by wishful thinking. You have to believe!

(define (move n from to spare)
  (cond ((= n 0) "Done")
        (else
         (move (-1+ n) from spare to)
         (print-move from to)
         (move (-1+ n) spare to from))))

Note to self: avoiding JavaScript whilst writing maths equations is tough. Implementing trees in LaTeX is even tougher.