Tail Recursion

We want to compute sum from 1 + 2 + .. + n

In an imperative programming language, we would write something like

sum = 0
for(int i = 1; i < n; i++){
    sum = sum + i;
}

In a functional programming language, we don't have looping mechanism. We will have to use recursion to get the task done

Version: 1
sum(n){
    if n = 0
    then 0
    else 0 + sum(n-1)
}

The second program will be slower, as there will be n activation record will be created for n function calls. For large value of n, it might cause No Memory Exception.

This problem can be solved by writing the above program differently,

Version: 2
sum(n, res){
   if n = 0
   then res
   else sum(n-1, res+n)
}

Initial call to the function will be, sum(n, 0).

If compared with the first version of the function, the second version of the function does not do anything after it receives the return value of calling function. The later version is called tail recursive function, caller does not do anything after the callee returns, it merely return the value returned by the callee. If a functional programming execution engine detects a tail recursive function, it does not create new activation records for callee functions, callee functions just reuses activation records of the caller.

Source
[0] https://www.coursera.org/learn/programming-languages/lecture/YZic1/tail-recursion

Do What I want

Imagine, I am letting a friend use my apartment. I can tell them how, I want them to clean the apartment -

How I want x to clean my apartment [2]

1. Take a picture of the place.
2. Focus on rooms you will actually use.
3. Pick up dirty clothes and towels.
4. Deposit empty glasses or dirty dishes into the sink.
5. Caddy your cleaning supplies.
6. Give the toilet, sink, and bathroom mirror a quick clean.
7. But just keep the shower curtain closed.
8. Tidy up the surfaces.
9. Toss stuff in baskets.
11. Take out the trash.
13. Take care of pet hair.
14. And vacuum
15. Fluff the couch pillows.
16. Spray a scent or light a candle.

Or I can tell them What I Want

Leave the apartment as it was before

Quicksort in C++. Code snippet taken from [0]

//Quick Sort Functions for Descending Order
// (2 Functions)
void QuickSort(apvector <int> &num, int top, int bottom)
{
      // top = subscript of beginning of array
      // bottom = subscript of end of array
      
     int middle;
     if (top < bottom)
    {
          middle = partition(num, top, bottom);
          quicksort(num, top, middle);   // sort first section
          quicksort(num, middle+1, bottom);    // sort second section
     }
     return;
}

//Function to determine the partitions
// partitions the array and returns the middle subscript
int partition(apvector <int> &array, int top, int bottom)
{
     int x = array[top];
     int i = top - 1;
     int j = bottom + 1;
     int temp;
     do
     {
           do  
           {
                  j - -;
           }while (x >array[j]);

          do
         {
                 i++;
          } while (x <array[i]);

          if (i < j)
         {
                 temp = array[i];    
                 array[i] = array[j];
                 array[j] = temp;
         }
     }while (i < j);     
     return j;           // returns middle subscript  }

Quicksort in Haskell. Code snippet taken from [1]

1. quicksort :: (Ord a) => [a] -> [a]  
2. quicksort [] = []  
3. quicksort (x:xs) =   
4.     let smallerSorted = quicksort [a | a <- xs, a <= x]  
5.         biggerSorted = quicksort [a | a <- xs, a > x]  
6.     in  smallerSorted ++ [x] ++ biggerSorted

>> What I want not How I want!


[0] https://mathbits.com/MathBits/CompSci/Arrays/Quick.htm
[1] http://learnyouahaskell.com/recursion
[2] https://makespace.com/blog/posts/how-to-clean-your-apartment-fast/