Когда задача естественно сводится к той же подзадаче (дерево, разбиение). Базовый случай и рекурсивный шаг. Минусы: стек вызовов, риск переполнения. Хвостовая рекурсия может оптимизироваться в цикл.