Recursion

1. Definition
2. Example : quick sort using recursion

• A recursive function is a function that calls itself until it is able to return the expected result.
• The base case of a recursive function is the point at which all the conditions necessary for computation of the result are met.
• When the base case becomes true, the recursive function stops calling itself and returns the result.
• The use of recursion often becomes necessary when a problem cannot be solved using for loops ...
• This is most likely because such problems have no predefined end or include branching factors.

// use a recursive function to compute the nth term of the fibonacci sequence
const fibonacci = (n:number):number => {
    // 1. BASE CASE
    // - base case met : the first 2 terms of the sequence cannot be
    //   computed using recursion for the fibonacci suite values are
    //   defined only for positive indices ...
    if (n === 1)
        return 1;
    else if (n === 0)
        return 0;

    // 2. PRE
    // - any operation that have to / may be completed BEFORE the
    //   function performs a recursive call ...
    void 0;

    // 3. RECURSION
    // - base case not met : recursive call
    const f = fibonacci(n - 1) + fibonacci(n - 2);

    // 4. POST
    // - any operation that have to / may be completed AFTER the
    //   function performs a recursive call ...
    void 0;

    // 5. RETURN
    // - return the end result of the current call ...
    return f;
};

• The most vital part of writing a recursive function is a clear and solid identification of the base case.
• Understanding of the PRE and POST steps are critical when it comes to implementing more advanced data structures.
• Of course, the PRE and POST step can never happen when the base case is met ...

• Quick sort is an interesting use case of recursion for array sorting that uses the "divide and conquer" approach.
• Sort by :
  • Selecting a pivot value in the input array (usually the last element).
  • Weak sort the input array (traverse it and use an index to swap elements accordingly) so as to produce 2 indices ranges :
    1. All the elements that are less than or equal to the pivot value (excluding the pivot value itself).
    2. All the elements that are greater than the pivot value.
  • Recursively calling the function with the 2 indices ranges.
  • The recursive calls have to stop when the start of the indice range exceeds its end (base case).
• Time complexity: between O(n * log n) and bubble sort's O(n²).

Notes :

• In Javascript, recursive functions can be sync or async.
• "Friends don't let friends recurse without the toolbox" 😁