I am doing Computer Science Engineering.
Can somebody please explain this topic with some real life examples.
I looked the internet and can’t find a basic definition all defintions are maths oriented.
In: 1
A recurrence relation is fundamentally a mathematical concept, so you’re not going to fully understand it until you put some time in to think about the math. But here’s an example of applying one.
Suppose you’re cutting a piece of paper. Each time you cut the paper, you take all the pieces and stack them on top of each other, then cut right down the middle.
Now we want a function for the number of pieces of paper produced by c cuts. Intuitively, we know we’ll go from 1 to 2 to 4 to 8 to 16… pieces of paper. We can therefore jump right to an analytic function: f(c) =2^(c-1). However, we can also write the recurrence relation. Each time we cut we double the number of pieces of paper we had before: r(c) = 2*r(c-1) for c>0. We also need to specify that we started with 1 piece of paper: r(0)=1.
Both ways of expressing the number of pieces of paper are valid and useful. For my money, the recurrence relation better expresses our intuition. Each cut produces twice as many pieces as the number we had before that cut. A computer is also very good at calculating the recurrence relation because it just means writing a simple function and calling it a bunch of times. This is not to say that a computer should have any trouble with 2^(c-1), but there are plenty of recursive expressions that don’t have an analytical equivalent (like the Fibonacci sequence), yet they’re still easy for computers. This is one reason why recurrence relations are such a big part of algorithms.
Latest Answers