Randomized vs Recursive Algorithm
Randomized algorithms incorporate a sense of randomness in its logic by making random choices during the execution of the algorithm. Due to this randomness, the behavior of the algorithm can change even for a fixed input. For many problems, randomized algorithms provide the most simplest and efficient solutions. Recursive algorithms are based on the idea that the solution to a problem can be found by finding solutions to smaller sub problems of the same problem. Recursion is widely used to find solutions to problems in computer science and many high-level programming languages support recursion.
What is a Randomized Algorithm?
Randomized algorithms incorporate a sense of randomness by making random choices that guides the execution of the algorithm. This is typically done by taking a set of random numbers generated by a pseudorandom number generator as an additional input. Due to this, the behavior of the algorithm may change even for a fixed input. Quicksort is a widely known algorithm that uses the concept of randomness and it has a running time of O(n log n) regardless of the input properties. Further, randomized incremental construction method is used for building structures like convex hull in computation geometry. In this method, the input points are randomly permuted and then inserted one by one in to the structure. Implementing a randomized algorithm is relatively simple than implementing a deterministic algorithm for the same problem. The biggest challenge in designing a randomized algorithm lies in performing asymptotic analysis for time and space complexity.
What is a Recursive Algorithm?
Recursive algorithms are based on the idea that the solution to a problem can be found by finding solutions to smaller sub problems of the same problem. In a recursive algorithm, a function is defined in terms of the earlier version of itself. It is important to note that this self referencing should have a termination condition to avoid referencing itself forever. The termination condition is checked before referencing itself. The initial step of a recursive algorithm is related to the basis clause of the recursive definition of the problem. The steps that follow the initial step are related to the inductive clauses of the problem. Recursive algorithms provide a simpler solution in many situations and it is closer to the natural way of thinking than the iterative algorithm for the same problem. But in general, recursive algorithms require more memory and they are computationally expensive.
What is the difference between a Randomized and a Recursive Algorithm?
Random algorithms are algorithms that use a sense of randomness by making random choices that could affect the execution of the algorithm, while recursive algorithms are algorithms that are based on the idea that a solution to a problem can be found by finding solutions to smaller sub problems of the same problem. Due to the randomness in the random algorithms, the behavior of the algorithm could change even for the same input (in different executions of the algorithm). But this is not possible in recursive algorithms and the behavior of a recursive algorithm would be same for a fixed input.