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
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!
Latest Answers