The legislators puzzle is well known and is actually an induction puzzle rather than recursion.

A better more easily understood version of the same puzzle is here : https://en.wikipedia.org/wiki/Induction_puzzles

Joesphine's Puzzle.