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
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