Understanding recurrence in algorithm design

Question

I have some ambiguity in recurrence, so I'll set the following questions:

(1) What does it really mean saying recurrence? Does it apply only when talking about divide and conquer?

(2) Assume I have this simple Algorithm:

sum <- 0
for i<- 1 to n
  sum <- sum + 1
return sum

How do I write a recurrence for this algorithm? I mean I understand this algorithm just does summation but how to transfer this into recurrence?

Thank you

Answer 1

I don't know what syntax you are using, but I suppose it would go something line this.

sub sum(n)  
   if n > 0 
     return 1 + sum(n-1)
   else 
     return 0
   end if
end sub

Answer 2

If you have a sequence of numbers $a_0,a_1,\dots , a_n, \dots$ and you have a relation between any $a_n$ and the terms preceding it, meaning that the "ancestor" terms generate the new one, that is a recurrence.
Then, once you know the values of the "pioneers" (those who are not generated by anyone), you can determine recursively all the generated sequel. In the example you made, the recurrence is
$S_n=S_{n-1}+1$ given that $S_0=0$, more formally $S_n=S_{n-1}+1 \quad | \; S_0=0$