Recurrence Relation: Definition Part-01
Unit-05
Recurrence Relation:
Definition
Examples (Fibonacci,
Factorial etc.),
Linear recurrence
relations with constants coefficients –
Homogenous solutions
Particular solutions
Total solutions
Problems.
Recurrence Relation:
Definition
1. A
recurrence relation is a mathematical equation that defines a sequence
of numbers, where each term of the sequence is expressed as a function of one
or more preceding terms.
2. In
other words, a recurrence relation is a way of defining a sequence by
recursively calculating each term based on the previous terms in the sequence.
3. Recurrence
relations are commonly used in many areas of mathematics,
computer science, and engineering, including number theory, combinatorics,
graph theory, algorithms, and optimization.
4. They
are particularly useful for analysing the time complexity of algorithms, as
well as for modelling dynamic systems that evolve over time.
5. Recurrence
relations can be linear or nonlinear, homogeneous or
non-homogeneous, and have different degrees of complexity.
6. Solving
a recurrence relation involves finding a closed-form solution that
expresses each term of the sequence as a function of the initial conditions and
the recurrence equation itself.
Examples
of Recurrence Relation: -
Here
are some examples of recurrence relations:
1.
Fibonacci sequence:
a. The
Fibonacci sequence is a well-known example of a recurrence relation.
b. It
is defined by the recurrence relation:
F(n) = F(n-1) + F(n-2),
where F(0) = 0 and F(1) = 1. This defines the sequence: 0, 1, 1,
2, 3, 5, 8, 13, 21, 34, ...
2.
Factorial function:
a. The
factorial function is defined recursively as follows:
n! = n * (n-1)!, where 0!
= 1.
b. For
example, 4! = 4 * 3 * 2 * 1 = 24.
3.
Towers of Hanoi:
a. The
Towers of Hanoi puzzle can be defined recursively as follows:
b. To
move n disks from tower A to tower C using tower B:
i. Move
n-1 disks from tower A to tower B using tower C
ii. Move
the largest disk from tower A to tower C.
iii. Move
the n-1 disks from tower B to tower C using tower A.
4.
Merge sort:
a. The
merge sort algorithm is defined recursively as follows:
b. To
sort an array A[1..n]:
i. If
n ≤ 1, return A
ii. Split
A into two subarrays, A[1..⌊n/2⌋] and A[⌊n/2⌋+1..n]
iii. Recursively
sort each subarray
iv. Merge
the two sorted subarrays into a single sorted array.
These
are just a few examples of the many different types of recurrence relations
that exist in mathematics and computer science.
No comments:
Post a Comment
Please do not enter any spam link in the comment box and use English and Hindi language for comment.