Процедура (или функция) считается leaf, если она не вызывает никакие другие процедуры или функции. И наборот, non-leaf функцией будет считаться та функция, которая вызывает другую подпрограмму/функцию. Таким образом, все рекурсивные функции будут non-leaf функциями.

Появление такой терминологии leaf/non-leaf связано с некоторым небольшим усложнением вызова для non-leaf функции для определенных архитектур (например MIPS). Это связано с тем, что non-leaf функция должна сохранить свой адрес возврата перед вызовом другой процедуры/функции. Для leaf-функции сохранять свой адрес возврата не требуется.

[Ссылки]

1. Leaf and Non-Leaf procedure in MIPS site:imvoid.wordpress.com.