We develop an operational theory of higher-order functions, recursion, and fair non-determinism for a non-trivial, higher-order, call-by-name functional programming language extended with McCarthy’s amb. Implemented via fair parallel evaluation, functional programming with amb is very expressive. However, conventional semantic fixed point principles for reasoning about recursion fail in the presence of fairness. Instead, we adapt higher-order operational methods to deal with fair non-determinism. We present two natural semantics, describing may-and must-convergence, and define a notion of contextual equivalence over these two modalities. The presence of amb raises special difficulties when reasoning about contextual equivalence. In particular, we report on a challenging open problem with regard to the validity of bisimulation proof methods. We develop two sound and useful reasoning methods which, in combination, enable us to prove a rich collection of laws for contextual equivalence and also provide a unique fixed point induction rule, the first proof rule for reasoning about recursion in the presence of fair non-determinism.