Recursive Algorithms

Last updated on October 10th, 2024 at 01:50 pm

Here, We will learn about recursive algorithm, recursion, recursive function, implementation, properties and examples of recursion.

Recursive Algorithms:

A Recursive Algorithm that calls itself repeatedly until a base condition is satisfied. Recursion is a technique in which function calls itself.

A recursive method that solves a problem by calling a copy of itself to work on a smaller problem is called a recursion step.

A Recursive function performs a task in part by calling itself to perform the subtasks. Recursive code is generally shorter and easier to write than iterative code.

public static long fib (long n)
{
    if (n <= 1)
        return n;
    else
        return fib (n-1) + fib (n-2);

Recursion is most useful for tasks that can be defined in terms of similar sub-tasks. For example, Sort, Search and traversal problems have simple recursive solutions.

Each recursive algorithm has at least 2 cases :

1. Recursive Case: a conditional statement that is used to trigger the recursion.
2. Base Case: a conditional statement that is used to break the recursion

Every recursive case must eventually lead to a base case

Properties of Recursion

1. The recursive solution is less efficient than the iterative solution due to the overhead of function calls
2. It uses a selection structure.
3. It is usually slower than iteration due to overhead of maintaining stack
4. It uses more memory than iteration.
5. It makes code smaller.
6. Infinite recursion can crash the system.

Examples of Recursive Algorithm

1. Fibonacci Series, Factorial Finding
2. Merge Sort, Quick Sort
3. Binary Search
4. Tree Traversals: InOrder, PreOrder and PostOrder
5. Graph Traversals: DFS (Depth First Search) and BFS (Breadth First Search)
6. Divide and Conquer Algorithms
7. Tower of Hanoi
8. Dynamic Programming Examples
9. Backtracking Algorithms

Related:

Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to 📧 contribute@totheinnovation.com. See your articles on the main page and help other coders.😎