Чтобы написать рекуррентное отношение для алгоритма, необходимо ли, чтобы алгоритм использовал рекурсию? Например: можем ли мы записать временную сложность линейного поиска как T (n) = T (n-1) + O (1)?
Нет, алгоритм не должен быть написан рекурсивно. Линейный поиск - хороший пример.
Кстати, используя стек, вы всегда можете «декурсивизировать» рекурсивную программу (т.е. вы можете сделать ее простой последовательной), не влияя на ее сложность.