To write a recurrence relation for an algorithm, is it necessary that the algorithm should use recursion? For example : Can we write time complexity of linear search as T(n)=T(n-1)+O(1) ?
No, the algorithm needn't be written recursively. Linear search is a good example.
By the way, using a stack you can always "derecursivate" a recursive program (i.e. you can make it plain sequential) without influencing its complexity.