Sunday, October 12, 2008

Recursion - adv/lim, factorial, Ackemann's fun

Recursion - adv/disadv, types, factorial, Ackemann's fun, etc.

What is Recursion?

It's a programming technique which facilitates writing simpler, shorter, and clearer code. A fucntion calling itself (either directly or indirectly) is called recursion. There are many programming situations which are very difficult (if not practically impossible) to be modelled without using recursion.

Advantages of using Recursion?

Recursive functions are simpler, clearer, and shorter as compared to their iterative counterparts.Recursive functions focus directly and precisely on the actual problem as compared to their non-recursive counterparts (which need to focus on other manipulations to avoid a recursion).

Disadvantages/Limitations of Recursion?

  • Inherently Inefficient - Recursive functions are inherently inefficient as they normally require relatively more space and time to execute. Every single call requires space to have its own set of local variables. In addition the caller needs to retain its own set so that when the callee returns it can resume its own execution. A function call requires some CPU time for context switching as well because the control requires to get transferred from the caller to the callee and then back to the caller. Such inherent overheads can't be eliminated from a recursive function and hence it'll almost always be relatively inefficient than its iterative counterparts. So why to use them? Because ther are certain problems which are very difficult to be designed and devloped (and in turn maintained) without using recursion. There may be cases where you don't really care too much about the performance instead on the correctness and maintainability of the solution. Recursion may be of use in those cases.
  • Difficulty in Debugging and fixing bugs - Does it sound little conflicting with what we discussed in the above point? Well... it's not actually. Recursion do facilitate better maintainability as the code is shorter, clearer, and directly focused towards the actual strategy. But, what if you're not very clear about the strategy? Unlike the iterative counterparts you don't get much access to the intermediate results and hence debugging a subtle issue may be frustrating at times particularly in the cases where the function calls itself a large number of times.

Types of Recursion?
  • Preemptive Recursion - the normal recursion where a function keeps calling itself unless some boundray condition is satisfied. It's normally achieved by decrementing/incrementing the passed arguments. Example: Recursive Factorial Algorithm where fact(n) calls itself with fact(n-1).
  • Non-Premptive Recursion: if a function calls itself from one of its parameters then such a recursion is called Non-Premptive Recursion. Example: Ackermann's function is an example of Non-Preemptie Recursion.

Ackermann_fun(m,n) = n+1 if m=0; Ackermann_fun(m-1, 1) if n=0; Ackermann_fun(m-1, Ackermann_fun(m,n-1)) otherwise.

It's important to note here that iterative counterparts of Preemptive Recursion is relatively easier to find as compared to the same in case of Non-Preemptive Recursion.

Recursive Factorial Function - Code

long int factorial(int n){

if(n == 0)
return 1;
return (n * factorial(n-1));

Recursive Factorial Function - Call Sequence for 'factorial(3)'

Geek Explains: factorial call sequence diagram



Amarjeet singh said...

thanks 4 ur my earlier problem
howevere this code does not work in my case
i solve this problem by another way

now there is a another problem

how can i displayed a Ms word file in a jsp file through java code

Geek said...

Hi Amarjeet,

I believe you're talking about your last comment posted on the article titled Structural Design Patterns >>

Please try to post follow-up comments on the same article/thread to maintain a better visibility.

Can you please share with us the actual error which you're getting while trying the suggested solution (in reply to your previous comment) to your AJAX Problem? What alternative approach did see you through finally?

Coming to your next problem, for reading a MS Word file using Java code you can use Apache POI. It's a Java implementation of the OLE 2 Component Document format which is widely used for reading Microsoft Word documents using Java. The latest release of Apache POI is POI 3.1-FINAL which was released on June 29, 2008.

How to use POIFS?

You first need load the file into the memory which you can do by using org.apache.poi.poifs.filesystem.POIFSFileSystem class. Once the file is loaded then you can read it by using the relevant APIs.

POIFSFileSystem fs;
fs = new POIFSFileSystem(inputStream);
catch (IOException e)
// either an I/O error or an incompatible POIFS structure
DirectoryEntry root = fs.getRoot();

Find all the steps of how to use Apache POI for reading a MS Word document here -

Hope it helps you getting your problem resolved.

Amarjeet said...

Hi geeks
but i download these jars
and with the help of these jars , i have successed in the display of
Ms word file in the jsp page

now regarding to my earlier problem
in Ajax
my case is that i want to use
means only that part of scipt is loaded which demand , and when user Click
other link , the old part of scripting is deleted and new is uploaded
becoz i want page loading is fast
So i want use Ajax
but Ajax is not worked here

when i use eval() function it execute scripting but it does not call a function in the script function
please go through the link

So i solve this problem by another way

function serviceCheck(jsc)

// alert(jsc.value);


function periodicChecker(str)
// alert("hi i m in periodicChecker method:"+str);
var service=str;
//alert(document.getElementById( alert(service)));
// alert(document.getElementById('"+service+"'));

var old = document.getElementById('"+service+"');
if (old != null)
delete old;
var head = document.getElementsByTagName("head")[0];
var script = document.createElement('script'); = ""+service;
script.type = 'text/javascript';
script.src = "../js/"+service+"_adpost.js";


i use this code 4 my problem

Geek said...

Hi Amarjeet,

HWPF is also a part of the Apache POI library only which supports all the MS Word document formats except the Microsoft Word 2007 .docx format (which is not based on the OLE 2 Component Document format). This library is still into its early stages of development and the future releases may handle .docx format as well.

Regarding your AJAX problem, I couldn't really understand your actual problem requirement in your previous comment(s) and hence suggested on the basis of what all I could make out of them. Anyway, what's important is that you are able to fix them now. Good work :-)

bumbu pecel bali said...

this is good post.
and you can go here

tanks very much.... :)