Это не "возникает" на самом деле. Отношение рекуррентности описывает поведение каждого шага решения рекурсивного алгоритма, более или менее сложность рекурсивной функции без учета затрат на рекурсивный вызов.
Например, двоичный поиск выполняет сравнение, а затем делит входной массив пополам, поэтому отношение повторения выглядит как T(n) = T(n/2) + ϴ(1), где ϴ (1) ("big-theta") относится к операции с фиксированным временем: сравнение, в данном случае.