Un sous-programme est dit récursif lorsqu'il fait appel à lui-même ou à des sous-programmes qui lui font références. On parle de récursivité directe lorsque le sous-programme s'appelle lui-même et de récursivité croisée lorsque plusieurs sous-programmes s'appellent mutuellement.