In several surprising situations, the elements satisfying a rational recurrence turn out to be Laurent polynomials in the initial values, rather than generic rational functions. This Laurent phenomenon arises in the study of cluster algebras and in a number of nonlinear recurrences. We will show how to use "caterpillar" trees to prove the Laurent phenomenon for a general class of recurrences, using as a basic example the quadratic recurrence for the Fibonacci numbers. We will then use the same technique to prove the Laurent phenomenon for the Somos-4 recurrence, which include elliptic divisibility sequences as a special case.