Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller, similar subproblems. ie Factorials.

There are two important things you need to keep in mind while doing recursion.

Base conditions ( where your code will stop or terminate).
Always assume that the function that will provide you with the value is already defined by some supernatural mechanism. (just use that function without thinking anything)

Example:

Finding the Factorial of a number !

There are two method you can use to calculate this, one is by using the loops and second is using recursion.

Loops Method:

int getFactorial(int n){

    int Factorial = 1; // intialise with 1
    for(int i = 1; i <= n; i++){
        Factorial = Factorial * i;
    }
    return Factorial;
}

Recursion Method:

int Factorial(int N){

    if( N == 1)  // base conditions
    return 1;

    else
    return N * Factorial (N-1); // recursion 
}

Both method have the time complexity equall to O(n).

Because, Factorial Function is doing a multiplication for N number of times. So, multiplication is constant time and same thing for N number times will result to O(n).

Application of Recursion:

Recursion is mainly used in stacks because when the base condition is fulfilled, the function returns the output to the calling function from where it was previously called. Hence, it's like push and pop.

One question here! We can see the time complexity is the same in both methods. So, which method is better to use?

We will always use the iteration method, i.e., the loop method, because in the case of the recursion method, the system has to check if there is empty memory and also needs to clear the stack when outputting the final result. All these processes take time, so it's not good to use recursion in the above example.

Practice:

// Check the question 3304 from leetcode.

The logic is as follows: suppose you have 'K', you need to decrease the value of K with each value you get after appending the word. Use a temporary variable to store the appended value that needs to be appended, and then append it to your word.

// Check the question 509 from leetcode.

The logic is as follows: No logic

Recursion