Recursion

Every passionate programmer through one stage of his career must have tried this out and surely must have loved it. .These are not the best methods to solve problems, yet many complex problems have their natural solution as recursive ones. We have a lots of recursive patterns in nature to be observed. One of the most common is  a tree of which each branch is a tree in itself (though smaller  in size).

  

Even some geometric shapes (fractals) can also be observed to have recursive patterns. You can observe the repeating pattern which is being created recursively.

       

My python function for Koch-Snow flake (fractal) .

def flake(self,length):
if length < 10:
self.move_forward(l)
self.c.update()
return
else:
self.flake(length/3)
self.rotate_left(60)
self.flake(length/3)
self.rotate_right(120)
self.flake(length/3)
self.rotate_left(60)
self.flake(length/3)

My code for the above is available here

Ackermann function

One of the most interesting recursive problems I’ve encountered.

def A(m,n):
if m == 0:
return n + 1
elif n == 0:
return A ( m - 1 , 1 )
else:
return A ( m - 1,  A ( m, n - 1 ) )

It will be observed the behaviour of the function can not be predicted unless the values of the parameters ‘m’ and ‘n’ are known.

This kind of programming might be simple enough but it has its own drawbacks too. These kind of programs might not be supported at production level as they might eat up the system stack and affect the performance drastically.

The size of process stack(8MB) on a standard linux machine can be easily be manipulated with ‘ulimit’ utility.

ulimit  -a

A simple C code to observe how a recursive program eats up the process stack.

void foo( int i ) {
char temp[ 1024 * 1024 ]; //1Mb of memory will be allocated from the stack-frame
printf (" %d \n", i );
foo ( i + 1 );

}

int main() {
foo( 1 );
}

Each time the ‘foo’ is invoked a new stack frame is created and a character array of 1 MB size is allocated from it  .So after a definite number of recursive calls when their is no more memory left it results in ‘‘segmentation-fault” when the program tries to allocate memory in the new frame( outside of process’s address-space).

Changing the size of the array ‘temp’ and size of stack using

‘ulimit    -s    <value>’

will give interesting results.

Tail-Recursion

Here the recursive procedure call is kept at the bottom of the procedure. This is of significant importance because an optimization technique can be used where no new stack frame is allocated for a recursive procedure call, instead the new frame can be used to replace the current frame.  This kind of optimization is called tail-call-optimization . Many functional Programming languages like to cope with this situation has implemented

I tried out some of both basic & classical recursive problems during my graduation years. Anyone who is interested with recursive patterns I suggest you to try out the below problems.

Eight Queens Problem  ,  Towers of Hanoi.  , Min-Max Algorithm   ,Creating  Fractal shapes  ,  SICP Chapter-1 (a lot of mind-bending problems are in there)