ajkqd (note: answer should be ode!)| sequence $c=$ | 1, | 2, | 3, | 2, | 3, | 4, | 3, | 4, | 5 | ← a finite sequence |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| sequence $b=$ | 1, | 2, | 3, | 2, | 3, | 4, | 3, | 4, | 5, | ... ← an infinite sequence |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Important! Note that an infinte sequence is a function with domain $\mathbb{N}$ (i.e. the non-negative numbers). If we take that view, we would say that $b(6) = 3$. We will freely go back and forth between viewing a sequence as a list, and viewing a sequence as a function with domain $\mathbb{N}$.
a = 1 , 2 , 5 , 10 , 17 , ...
| | | | |
a0=1 a1=a0+2i-1 a2=a1+2i-1 a3=a2+2i-1 a4=a3+2i-1
=1+2*1-1 =2+2*2-1 =5+2*3-1 =10+2*4-1
=2 = 5 =10 =17
It looks like we are getting the same sequence as in the
previous section. Can we prove it?
I.e. can we prove that the sequence given implicitly by
$$
\begin{array}{l}
a_i = a_{i-1} + 2\cdot i - 1,\\
a_0 = 1
\end{array}
$$
has closed form $a_i = i\cdot i + 1$?
Of course we can verify it by computing as many elements of the
sequence as we want, but to prove that this is true for any
non-negative $i$ ... well it requires induction, of course!
[Do by hand recursive style (building a stack)]
Doesn't this look just like recursion?!?!?! In fact, we can translate the implicit form directly into a recursive function:
int a(int i) {
if (i==0)
return 1;
else
return a(i-1) - 1 + 2*i;
}
So the implict form of a sequence and recursion in programming
have a very close relationship. In fact, an implicit form of a
seqeuence (or, equivalently, the implict form of a function
with domain $\mathbb{N}$) is called a
recurrence relation.
Hopefully the above
discussion helps you see why it has this name!
We won't give a formal
definition of "recurrence relation" yet, because there are
actually many different kinds of
recurrence relations and we're not ready to distinguish between all the
different types and/or give a super general definition.
Important! Pretty much the central problem related to recurrence relations is this: given a recurrence relation for function f, find a closed form representation for f.
In the above we did just that. Of course we were lucky. We generated some terms in the sequence from the recurrence relation, and we noticed that they matched a sequence we'd seen before and knew a closed form for. Then all we had to do was prove that the two matched not only for the few terms we'd generated, but for all terms ... which of course required induction. What happens if we don't get lucky, and the sequence we have a recurrence relation for doesn't match something we already know in closed form? Well ... we'll spend the next several classes scratching away at the tip of that particular iceberg!
1: void prn(Node* L, int n) {
2: if (n == 0)
3: return;
4: Node* p = L;
5: for(int i = 0; i < n-1; i++)
6: p=p->next;
7: cout << p->data << ' ';
8: prn(L,n-1);
9: }
To understand how efficient/inefficient this algorithm is, we
want to count, for example, how many ->s to check
values from linked list nodes are
executed. Of course, this depends on $n$, so the number of
->s executed is a function of $n$: let's call it
$T(n)$. If we look at the code we get n-1 ->s from
the loop on lines 5-6, and one -> from line 7.
Plus, we get $T(n-1)$ ->s from the call on line 8.
Since the $n=0$ case on line 2 just returns immediately, $T(0)=0$.
So:
$$
\begin{array}{l}
T(n) = n+T(n-1)\\
T(0) = 0
\end{array}
$$
Viola! Trying to understand how much work our code does leads
us straight to a recurrence relation. This is one of many
reasons that recurrence relations are important to computer science.