Recursion - Data Structures and Algorithms

I am planning to write a series of posts covering complete Data Structures and algorithms in beginner friendly way. I will be using java to explain the examples.

In Data Structures and Algorithms Recursion is one of the first concept which is very important to understand, since it makes you think in cycles.Its like a fractal but it should have an end.

Example Problems on Recursion:
https://github.com/akshayrak/Data-Structures-and-Algorithms/tree/main/src/recursion

Important points to remember in Recursion:

1.Recursive function is a function that calls itself.

public static int factorial(int n) {
        return n*factorial(n-1);
    }

2.Recursive function should cover all the conditions that could arise.

public static int factorial(int n) {
        if(n==1||n==0) {
            return 1;
        }
        return n*factorial(n-1);
    }

3.We should also take care of exceptional situations also.

public static int factorial(int n) {
        if(n==1||n==0) {
            return 1;
        }
        if(n<0) {
            return -1;
        }
        return n*factorial(n-1);
    }

4.It uses Stack Memory to remember the functions it has called, so once the last function is executed, it keeps popping out the functions in Last in First out order.
Note: Stack is one of the data structure that follows first in last out or last in first out, just think about stack of books

5.All the problems that can be solved using Recursion can also be solved using iteration, iteration is efficient when you compared to space and time complexity of recursion but recursion is easy to code than iteration.

public static int factorial(int n) {
                int count = 1;
        for(int i = 2;i<=n;i++){
                   count = count*i;
           }
           return count;
    }

6.So we can use recursion only when code clarity is more important than the time and space complexity, so we wont be using recursion in time critical cases (devices where life depends on time) and low storage cases (low stack memory devices).

7.We commonly use recursion in trees.

8.Recursion can be very slow if not implemented properly.

Let me know if I need to add anything else or in case of any doubts comment down below

Photo by Mika Korhonen on Unsplash