data structure are user to organize our data in a specific way to make the operation on the data will be easier and faster. The steps taken on the data structure to get the results out of the raw data is called algorithm.
Data structure is of 2 types-
- Primitive - The data structure which is provided by the language we ra working on is called primitive dta structure. ex - Integer, Double, Float, Boolean in case of Java.
- Non-primitive - the data structure which is created with the help of the primitive DS is non-primitive DS.
This can again be categorized into 2 types.
- Physical - DS which is physically present in the memory. ex - Array, linked list.
- Virtual - DS which is user defined and not directly present in memory. this takes help of physical and primitive DS to work. ex - stack queue, tree, graph.
Any operation which is performed repeatedly with different data set to arrive at output is called a recursion. Here in every step we try to make the problem smaller and at last get the result.
In real world we use this in case of searching in binary tree search.
In the most popular kind of algorithms like greedy, divide and concur and dynamic programming recursion is used heavily. In case of tree and graph its kind of mandatory to use recursive programming to get the result.
A recursive code block has 2 elements -
- Recursive code
- break condition
Lets say we have a recursive method.
fun foo(input : Int){
if(input == 1){
return
}
foo(input - 1)
}
foo(3)
This code will save its calls in stack as follows
Stack Memory |
---|
foo(2) |
foo(3) |
this is multiplication of 1 till n. where n is a non negative integer.
4! = 1 * 2 * 3 * 4 = 24
fun factorial(number : Int){
if(number == 1)
return 1
factorial(number * factorial(number - 1))
}
factorial(4)
//first recursion
//factorial(4) >> 4 * factorial(3)
//factorial(3) >> 3 * factorial(2)
//factorial(2) >> 2 * factorial(1)
//return 1
//return 2 * 1
//return 3 * 2
//return 4 * 6
//return 24 <<result
The function has a break condition and a recursion code block.
this is the contentious addition of previous two number in a series. the first two number are 0 and 1. which makes it 0, 1, 1, 2, 3, 5, 8 ...
fun fibo(fibboIndex : Int){
if(fibboIndex == 0 || fibboIndex == 1)
return 1
return (fibo(fibboIndex - 2) + fibbo(fibboIndex - 1))
}
fibbo(5)
/*
fibbo(3) + fibbo(4)
fibbo(1) + fibbo(2) + fibbo(2) + fibbo(3)
1 + fibbo(0) + fibbo(1) + fibbo(0) + fibbo(1) + fibbo(1) + fibbo(2)
1 + 1 + 1 + 1 + 1 + 1 + fibbo(0) + fibbo(1)
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
8 << Result
*/
- We can solve the problem of recursion also with iteration.
- Also recursion has disadvantage of space and time over iteration, and iteration takes teh head in these case.
- We can use recursion when
- We can divide problem into similar sub problems.
- We can compromise with time and space.
- We want a quick solution over a efficient one.
We use recursion in stack, tree, sorting, divide and concur, dynamic programming.
This is the measurement of performance of any algorithm.
- Omega ( Ω ) - Lower bound of an algorithm. minimum run time of an algorithm. or we can say that the best case scenario for the algorithm.
- Big-o ( O ) - Upper bound for an algorithm. this is the worst case for the algorithm.
- Theta ( θ ) - Decides if the upper and lower bound of an algorithm are same or not. or in other words it says what is the average time for and algorithm.
lets say we have an array - 5, 10, 45, 43, ..., 34, 5, 23, 1, ...
and now if we want to search for 43. and lets say it took 10 n time to find the value in the array. where n is time taken to traverse 1 element.
- here the omega for the algorithm would be - n
- big-o would be - number of elements * n
- theta would be - n / 2
- order of 1 or constant time complexity.
- order of log n
- order of n - linear time complexity
- order n log n - linear logarithmic complexity
- order n Sq
- order n Cube
- order 2 power n - exponential time complexity