It is well known that computer science students often strug- gle to understand recursion and theory of computation (ToC) students are no exception. The difference is that ToC stu- dents encounter recursion not while programming, but while writing proofs. Fortunately, educators have already devel- oped many strategies for helping students write recursive programs, with many of the ideas coming from the func- tional programming community. This paper explains how we adapted one of these ideas, that of “Design Recipes” from the “How to Design Programs” textbook, into a technique to help theory of computation students write inductive proofs. With our approach, we have seen improved results over sev- eral semesters. Even better, students leave the course with a deeper understanding of the fundamental ideas and rely less on memorizing opaque rules and copying from tangentially related examples.