Recursion is a notoriously difficult concept to learn. This paper presents a structured approach to teaching recursion that combines classroom lectures and self-paced interaction with Cargo-Bot, a video game in which users solve puzzles using a simple visual programming language. After mapping Cargo-Bot games to a set of learning goals, we devise a lesson plan that uses Cargo-Bot game playing to scaffold key concepts used in writing recursive Java programs. We empirically evaluate our approach using 204 undergraduates enrolled in a CS2 course, and we show strong statistical evidence that our approach improves student learning of recursion over traditional lecture-based instruction alone.