Tail recursion–in detail

“The beauty of recursion is that!!.. - the beauty of recursion.”

Author speaks

  Sorry for not publishing any post nowadays. Tied up with lots of personal work. Now, would love to continue the series without gaps at least for some time. This promise is Without any GURANTEE, WARENTEE or any BONDS. :)

Metaphor

  If you catch something by tail, it tries to attack you using its head. :D

I think the below image will make you remember very well what is tail recursion.

Introduction

   Tail recursion is something that is more native to functional programming languages. In Maths, a tail recursive function is a function that expands itself.

Say, g(x) = f(x)

Then, tail recursion happens like this formula,        f(x) = f(g(x))

This means, f(x) = f(f(x)) = g(f(f(x)) = f(f(f(x))) … it goes on

This is purely useful for writing an mathematical logic which has a specific end condition. But this kind of recursion is majorly used in optimization of stack space in C++ and similar languages. Even some dynamic languages support this recursion type. But python doesn’t support it because of simple inherent problems for developers while using tail recursion.

Concept

   As i explained, tail recursion is mostly used for optimization & mathematical problem and widely popular in functional programming. The most and the perfect way a tail recursion works is really good for designing mathematically a computer program. But if you are normal novice software engineer, you just use this for optimization and only when its necessary because of its demerits:

• Stack doesn’t contain any footprint of the recursion happening. Compiler tries to expand the cycling recursion into instructions without using stack
• As there is no stack data, no way to debug such programs easily.
• Compilers might sometime fail to make the right jumps and data corruption can never be captured.

Already developers fight with pointers when this havoc adds more headache to it.

Programmers can think tail recursion as, just processing things using arguments itself and keep the returned value as the recursive call to the function. This makes the compiler to process the return value which expands the recursive calls in the single stack frame!!

Code

#include <iostream>

int fib(int n)

{

    if(n==0)

        return 0;

    else if(n==1)

        return 1;

    else 

        return fib(n-1) + fib(n-2);

}

int main()

{

    std::cout<<fib(7);

    return 0;

}

• Assembly is generated with tail optimization only when release mode is selected with Visual Studio C++.
• You can note that there is no stack footprint by the executable created by this, by tracing the disassembly.

Conclusion

Is it good or bad? based on the need and stack space savings requirement.

Infix, Prefix and Postfix notations

“Notations are created for easy processing of expressions. Polish and Reverse Polish Notations are popular ones. Normal notation is human readable.”

Introduction

  There are 3 kinds of expression notations: infix, prefix and postfix.

• Infix: is human readable. (2+3)*4
• Prefix: is readable with stack. Expressions first, values next. *+234
• Postfix: Values first, expressions next.  23+4*

Read more about the prefix notation here: http://en.wikipedia.org/wiki/Polish_notation

Prefix & postfix doesn’t need to use brackets and can be easily represented using stack or tree.

The main advantage is that we don’t need to care much about the precedence as in Infix notation.

Code

/*

Scan the given prefix expression from right to left

for each symbol

 {

  if operand then

   push onto stack

  if operator then

   {

    operand1=pop stack

    operand2=pop stack

    compute operand1 operator operand2

    push result onto stack

   }

 }

return top of stack as result

*/

void main()

{

    char* str = "*-5 6 57";

    StackList opStack;

    int d, sum = 0;

    int result=0;

    int count = 0;

    char* rstr = str;

    while(*rstr != '\0') rstr++;

    rstr--;

    while(rstr > str-1) {

        if(isdigit(*rstr)) {

            d = *rstr - 48;

            if(count == 0) sum = d;

            sum += d*count*10;

            count++;

        } else {

            if(sum != 0) {

                opStack.push(sum);

                sum = 0;

                count = 0;

            }

            switch(*rstr)

            {

                case '+':

                    opStack.push(opStack.pop() + opStack.pop());

                    break;

                case '*':

                    opStack.push(opStack.pop() * opStack.pop());

                    break;

                case '-':

                    opStack.push(opStack.pop() - opStack.pop());

                    break;

                case '/':

                    opStack.push(opStack.pop() / opStack.pop());

                    break;

            }

        }

        rstr--;

    }

    cout<<opStack.pop();

}

• We need to come in reverse and push into stack the integers
• When we see a operator, we need to operate the top 2 elements in the stack.
• Note that, we use space as the delimiter between 2 digits. For operators, we don’t need that
• In the stack we will have the only element which is the processed output of the expression

Implement a Stack using Linked List

 

Question

  You need to implement a stack using singly linked list so that POP and PUSH takes O(1) similar performance of an array. How would you do that?

Concept

  We know about LIFO in a stack. We have to just maintain the element added to the linked list at the top. Then you will get a PUSH at the top with O(1) and POP at the top with O(1).

Code

class StackList 

{

    struct ListNode {

        int data;

        ListNode* next;

    };

    ListNode *head;

public:

    StackList() : head(NULL) {}

    void push(int data);

    int pop();

};

void StackList::push(int data)

{

    ListNode* n = new ListNode;

    n->data = data;

    n->next = head;

    head = n;

}

int StackList::pop()

{

    if(head == NULL)

        return -1;

    int tdata = head->data;

    ListNode* next = head->next;

    free(head);

    head = next;

    return tdata;

}

void main()

{

    StackList obj;

    obj.push(5);

    obj.push(3);

    obj.push(2);

    obj.push(10);

    cout<<obj.pop();

}

• Add elements to the head node
• Remove elements also from the head node

Implement push, pop, min in O(1) performance

 

Introduction

   This is a popular interview question found in a site. (ihas1337code). You need to implement push, pop, min all with just O(1) performance. You can use extra space and you can do any push & pops. Every time you should get the minimum in the stack using the min function.

Concept

  Do do this, you need 2 stacks. One which maintains all the minimums found until then and one which contains all the numbers.

For example, the main stack is.

3

2

10

1

7

5

9

The stack with all the min’s found will be

1

5

9

NaN

 

Now, when you pop from the main stack, make sure that you pop the min stack as well only when the element is equal to the popping element.

So, if we have pop-ed 3,2,10, we will still have 1 as min in the min stack. Remove 1 as well in the main stack, you must remove 1 in the min stack as well. Now, definitely 5 is the min.

  With this approach, you can implement pop, push, min all in O(1).

Code

class PerStack

{

    int arr1[100];

    int arr2[100];

    int top1;

    int top2;

public:

    PerStack() : top1(0), top2(0) {

        arr2[0] = INT_MAX;

    }

    void push(int val)

    {

        arr1[top1++] = val;

        if(val < arr2[top2] )

        {

            arr2[++top2] = val;

        }

    }

    int pop()

    {

        if(arr1[top1] == arr2[top2])

            arr2[top2--] = INT_MIN;

        return arr1[--top1];

    }

    int min() {

        return arr2[top2];

    }

};

void main()

{

    int A[] = {9,5,7,1,10,2,3};

    PerStack n;

    for(int i=0; i<7;i++)

        n.push(A[i]);

    cout<<"minimum : "<<n.min();

}

Stack –An introduction

”Pile of things is a stack!!.. Why would such a pile used in computers? Early computers read memory in a stack form since memory operations are too costly those days. The stack based systems are a big failure when hardware bandwidth and cost reduced. Then too, register stack came which is faster to access. Even some system caches are maintained as stack and a raw machine code flow is maintained on a stack. So, stack became inevitable for low-end systems not for high end”

Metaphor

   Think about the old machines which reads punch cards and store the bits. These machines can only read one bit at once and write one at a time. They are very slow that, block read cannot be done. For a char(1-byte per cycle) based systems like this and if the data stored has a property of Last in first out (LIFO) then a stack is used to maintain the history.

   History gives a indirect meaning to a stack. The first entered element goes to the last!! So most valid use cases of a stack pile is to dump old data and get the latest one at the top!!

Concept

  Stack is a data structure. Not a data organization. We already discussed that all data structures have static and dynamic data organizations. Static is usually constructed using array and dynamic using linked list. Stack as we discussed till now, can be limited to size using array. It can be made unlimited until the full memory is exhausted using linked list.

    The major operations in a stack are:

     - INSERT – which is the PUSH operation. dump the element to the stack

     - DELETE – which is the POP operation, pick the latest element in the stack

Always, we should have the latest element at the TOP of the stack. On every PUSH, stack overflow possibility need to be checked using STACK-FULL. On every POP, stack underflow need to be checked using STACK-EMPTY.

Code

   1:  const int SIZE=10;

   2:   

   3:  template<class T>

   4:  class Stack

   5:  {

   6:      T arr[SIZE];

   7:      int top_idx;

   8:   

   9:      int top() const    {    return top_idx; }

  10:   

  11:      bool stack_empty() const {  return (top_idx == -1);     }

  12:   

  13:      bool stack_full() const { return (top_idx+1 > SIZE-1); }

  14:   

  15:  public:

  16:      Stack() {

  17:          top_idx = -1;

  18:      }

  19:   

  20:      bool push(T val)    {    

  21:          if(stack_full())

  22:              return false;

  23:          else {

  24:              arr[++top_idx] = val;

  25:              return true;

  26:          }

  27:      }

  28:   

  29:      bool pop(T& val) {

  30:          if(stack_empty())

  31:              return false;

  32:          else {

  33:              val = arr[top_idx];

  34:              top_idx -=1;

  35:              return true;

  36:          }

  37:      }

  38:  };

  39:   

  40:  void main()

  41:  {

  42:      Stack<int> sobj;

  43:      int pop_val;

  44:      for(int i = 0; i<12;i++)

  45:          sobj.push(i);

  46:   

  47:      for(int i = 0; i<12;i++)

  48:          sobj.pop(pop_val);

  49:  }

Problems while coding
- tried C++ template object for stack :). so lots of problems. Const-ness creation should be done carefully, there is something called logical and bitwise const. We will study about it later as it is related to C++ concepts.
- All the members in a class are by default private.. :D very basic problem
- You cannot initialize a member variable inside a class. It should be static or const to be initialized because, class is only a compile time structure!! Not runtime one
- incrementing the top and decrementing it.. confusing!!.. top should be -1 if array index is 0. if linked list is used, have top as zero and continue counting..
- stack full is determined when top+1 exceeds the size. for linked list case, size is up to memory full. So, just memory full check will do!!