When do children acquire the ability to understand recursion-that is, repeated loops of actions, as in cookery recipes or computer programs? Hitherto, studies have focused either on unconscious recursions in language and vision or on the difficulty of conscious recursions-even for adults-when learning to program. In contrast, we examined 10- to 11-year-old fifth-graders' ability to deduce the consequences of loops of actions in informal algorithms and to create such algorithms for themselves. In our experiments, the children tackled problems requiring the rearrangement of cars on a toy railway with a single track and a siding-an environment that in principle allows for the execution of any algorithm-that is, it has the power of a universal Turing machine. The children were not allowed to move the cars, so each problem's solution called for them to envision the movements of cars on the track. We describe a theory of recursive thinking, which is based on kinematic simulations and which we have implemented in a computer program embodying mental models of the cars and track. Experiment 1 tested children's ability to deduce rearrangements of the cars in a train from descriptions of algorithms containing a single loop of actions. Experiment 2 assessed children's spontaneous creation of similar sorts of algorithms. The results showed that fifth-grade children with no training in computer programming have systematic abilities to deduce from and to create informal recursive algorithms.
Keywords: Abduction; Deduction; Informal algorithms; Kinematic simulations; Recursion.