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.
The most familiar example of a recurrence relation for most people is probably the Fibonnacci series: 1, 1, 2, 3, 5, 8, 13, 21, etc. It’s a recurrence relation because each next term in the series is found by doing some calculation on the previous terms in the series. In the case of Fibonacci, that calculation is adding the previous two terms to get the next one. So to work out the 10th Fibonacci number, you have to know both the 9th and the 8th, and to get the 9th you need to know the 8th and the 7th, and so on and so on. Not sure if that’s a satisfying “real world exampele”, but despite that I think Fibonacci is the easiest example to understand.
You can contrast that to say, the sequence of square numbers: 1, 4, 9, 16, 25, etc, which is not a recurrence relation. To get the 10th square number, I don’t need to know what any other number in the sequence is, I just multiply 10 by itself to get 100 and I’m done. Therefore, the sequence of square numbers is said to have an “explicit formula”, rather than a recurrence relation.
You actually can write an explicit formula for the Fibonnaci numbers, as well as a recurrence relation to define the square numbers, but it’s trickier (the square number one is only a little trickier – an exlplicit formula for Fibonacci is insanely hard). It’s kind of a neat puzzle to try and work out the recurrence relation for squares 🙂 Hope this helps!
I’m going to ELI computer science student, since OP said that’s what he is.
Programmer’s definition of recurrence relation: You have a very long array. The nth element of the array is calculated from the K previous elements. (That’s it!)
So an example of a recurrence relation is the Fibonacci sequence, where each number is calculated from the previous two numbers:
f[0] = 1
f[1] = 1
for i from 2 to n:
f[i] = f[i-2] + f[i-1]
The Fibonacci sequence is probably the most famous non-trivial recurrence relation. For Fibonacci, K=2 is how many elements the formula’s allowed to look back. (You can think of K as how many elements you’d need to keep in memory to calculate the next element if your program streams the elements to a file instead of putting them in an array in memory.)
There are lots of possible recurrence relations. How many initial elements there are, what values those initial elements have, what formula is used to calculate the next element, and K can all be different.
If the formula you use is a linear function it’s called a *linear recurrence relation*. (The Fibonacci sequence is an example of a linear recurrence relation.) This is also a linear recurrence relation:
f[i] = 3*f[i-1] + 5*f[i-3] – 24*f[i-6]
If you have a linear recurrence relation, there’s a way to find a formula you can use to calculate the nth term directly. So if you want to find the thousandth Fibonacci number, without the formula, you’d have to run the loop a thousand times. With the formula, you can simply calculate it directly. The [Wikipedia article](https://en.wikipedia.org/wiki/Linear_difference_equation) explains more about how to find these formulas, but it may be more mathy than you’re comfortable with.
It’s only tangentially related, but here’s a [Mathologer Youtube video](https://www.youtube.com/watch?v=e7SnRPubg-g) about the Fibonacci and Tribonacci numbers, and their formulas for the nth element.
Latest Answers