Lightbox feature

I've added a cool new lightbox feature to this blog. Rather than explain it, it's a lot easier to demonstrate. In order for the lightbox feature to work, you have to click on the image on the website, as it uses Javascript which does not get loaded when viewing through an RSS reader.

To see it in action, just click on any of the images posted to the blog and see what happens.

If you like it, you can get the code from here.

Enjoy!

NTFS Junction

One of my gripes with Windows XP has been the lack of proper symlinks. They have shortcuts, but a shortcut is not a symlink. Try this:

1. Create a shortcut to C:\WINDOWS and place the shortcut in C:\
2. Rename the shortcut to "mytemp"
3. Open the command prompt by doing Start->Run..->cmd and type cd C:\mytemp

If try that, you will find that you cant access the directory. This is because a shortcut doesn't create a link exactly, but creates a file mytemp.lnk. Now try cd C:\mytemp.lnk, and it will find the file, but since it is only an ordinary file, you can't do a change directory to it. In other words, a shortcut is nothing but a file which has special meaning only to Windows Explorer.

Well, it turns out that NTFS does support actual proper symlinks. These are called Junctions in NTFS. Junctions also allow you to mount filesystems at a mount point much like how it is done in UNIX. The only problem is that there is no way to create Junctions with Windows XP. That was until I found this awesome utility which allows you to create proper junctions on your NTFS drive. This is something that I have been wanting for ages. If you ever wanted proper symlinks on windows, you just have to check out Junction .

Recursion Part 6: References and Further Information

The following is a part of a series of articles I had written on recursion.

---

This, the final part of the series contains sources for the articles and where to get further information.

All Parts:

Recursion Part 1: Introduction to recursion
Recursion Part 2: Tail recursion, Accumulators and Iteration
Recursion Part 3: Exercises in tail recursion
Recursion Part 4: Tree Recursion and Dynamic Programming
Recursion Part 5: Structural and Generative Recursion
Recursion Part 6: References and Further Information

---

The best way to learn about recursion is to learn a language that doesn't support iteration. Scheme is a good language to learn in this context. A Scheme interpreter can be got from here

Another good resource is the 6.001 course from MIT. The course material for this course is available for free.

Two highly recommended books:
1. Structure and Interpretation of Computer Programs (also called as The Wizard Book). There is an Indian edition, but not very easy to find.
2. How to design programs. This book is also available in an Indian Edition, but there is often not much stock.

Both books use the Scheme language, so they also serve the purpose of those trying to learn Scheme. Both books are also available for free on the Internet.

For more on dynamic programming, see Chapter 15 of the book 'Introduction to Algorithms' by Cormen, Leiserson and Rivest. This is a college textbook and is available in any bookstore. Most other books on algorithms also include a chapter on dynamic programming. Otherwise searching Google for "dynamic programming" will provide lots of articles on this topic.

---

Any questions? Comments? Please leave a comment using the comment form below.

This post is a part of the selected archive.

Recursion Part 5: Structural and Generative Recursion

The following is a part of a series of articles I had written on recursion.

---

This part deals with two areas for which recursion is commonly applied. The first, called structural recursion, is used to traverse through different parts of a data structure, processing each part in some way. The second, called generative recursion, is used when we want to divide a problem into smaller subproblems, which are then solved.

All Parts:

Recursion Part 1: Introduction to recursion
Recursion Part 2: Tail recursion, Accumulators and Iteration
Recursion Part 3: Exercises in tail recursion
Recursion Part 4: Tree Recursion and Dynamic Programming
Recursion Part 5: Structural and Generative Recursion
Recursion Part 6: References and Further Information

---

Let us start of with structural recursion. Here is an example, an inorder traversal of a binary tree:

void inorder(node element)
{
    if (NULL == element) {
        return
    }
    inorder(element->left);
    process(element->data);
    inorder(element->right);
}

This is a classic case of structural recursion. Each recursive call processes a part of the binary tree. Put together, we process all the elements in the tree. Structural recursion is often used when dealing with self-referential data structures like lists, trees and graphs. Functions to deal with these structures are hard to implement with iteration¹, and even if we do manage to implement them with iteration, the resultant code is often very difficult to understand. Such code is best left as recursive.

In some cases, it is possible to modify the data structure itself so that common operations can be implemented iteratively. An example of this is the threaded tree data structure that modifies the classic binary tree to allow for iterative traversal.

In any case, except for exceptional cases, it is best to use recursive algorithms to implement structural recursion

Generative recursion is often used when we want to break up a problem into similar subproblems. The subproblems are solved and the results combined to get the final solution. Solving the subproblems in turn requires recursion to break the problem into smaller subproblems, and so on until we reach a trivial case. The recursive examples of factorial and fibonacci number calculations and the well known quicksort are examples of generative recursion.

Look at this fibonacci program again and convince yourself that it uses generative recursion:

int fibonacci(int n)
{
    if (0 == n) {
        return 0;
    } else if (1 == n) {
        return 1;
    } else {
        return fibonacci(n - 2) + fibonacci(n - 1);
    }
}

Generative recursion that operates on a known finite set (eg: fibonacci(n) operates on integers between 0 and n) are good candidates for a dynamic programming approach. Generative recursion that operates on large or unknown sets (eg: functions that work with real numbers often fall into this category) are usually not condusive to dynamic programming. Some cases of generative recursion may have good iterative solutions, but this has to be considered on a case by case basis. In most cases, it is best to just leave them recursive.

Of course, all the above only applies to tree recursion. Tail recursion, whether structural or generative can always be converted into iteration.

---

¹ The exception is linked lists. Linked lists usually result in tail recursion which can be converted to iteration.

---

Any questions? Comments? Please leave a comment using the comment form below.

This post is a part of the selected archive.

Agile is not XP

I recently heard this podcast with Dave Thomas. Dave has talked on many occasions about the Dreyfus model of Skill Acquisition, which is similar to Shu Ha Ri. He also talks in the podcast about some Agile practitioners being dogmatic in their views. So in a sense, listening to the padcast made me go and write these posts, something that I've been meaning to do for a long time anyway.

In a previous post I had said "Sometimes I think that the term Agile has been co-opted by the XP and Scrum groups, but that's a topic for another post."

What is agile development? In theory, agile processes follow the four points of the agile manifesto. However, most people use the term "agile" to actually refer to either XP or Scrum, and consequently practices from these processes are invariably attached to the term "agile". This is a pity, because agile is a general term that refers to a host of different methodologies, many of which differ very markedly from XP.

For instance, while XP says no big design up front, both FDD and DSDM have distinct modelling phases at the start of a project. Similarly, XP minimises documentation, whereas say Crystal Clear does emphasise certain documentation. This obviously irritates a lot of people. Alsitair has an AgileIsntXp page on his twiki.

I also agree with Dave's comment that agilists can sometimes be dogmatic. How many times have we seen arguments along the lines of "thats big design up front, so its not agile", never mind if it helped solve the problem or not. I was just searching around for more info on the No Fluff Just Stuff conference when I came across this link which just illustrates the point (see section on Pragmatic Tracer Bullets).

If you are having a big discussion on the level of "is this big design up front or not?" then it's a lost cause already, because that is the wrong question. The question should be "will it help me produce working software?" and if the answer is yes, then you do it. Of course, as we saw in the Shu Ha Ri post, beginners who are just starting out with the process need clear rules, and "no big design up front" is a clear rule, whereas "will it help me produce working software" is not so easy to answer. You need to be in the Ha or Ri phase to answer this one.

There is a fundamental paradox here, because agile was developed in response to the "rules" based ISO/CMMI processes, replacing them with a more intuitive understanding of project management as placed out in the agile manifesto. This is great for the intermediate and expert project managers, what about those just starting out on the process who need clear rules? We need to put in certain rules and best practices to help beginners. But in the end, guiding beginners is all the rules are for. They are not "best practices" to be followed by everyone in every situation.

Finally, go read James Bach's posts on What is agile methodology? and No Best Practices, both of which hit the nail squarely on the head.

This post is a part of the selected archive.

Shu Ha Ri

Shu Ha Ri.

What is Shu Ha Ri?

Shu Ha Ri is a Japanese term, usually applied to martial arts training, to describe the stages in learning a skill. The first word, "Shu", means "to obey". The second word, "Ha", means "to break free". The third word, "Ri", means "to depart".

These three words describe the three stages of learning. When you are a novice, just starting out on a new skill, you need clear, precise, unambiguous instructions. You do not understand the bigger picture or the intent for the instructions. Any further background only confuses you. You are at the "Shu" stage - "to obey". After a while, you begin to learn the instructions, and the question that comes up is "why?". Why am I following these rules this way? What is the intent behind them? You slowly start to understand the context behind these rules. At this point, you have broken free of the rules. You are at the "Ha" stage - "to break free". Finally, you become an expert. You not only know the rules and the reasons, but you are in a position to create your own rules. You no longer follow the old rules, but follow your rules, crafted by you, just for you. You are at the "Ri" stage - "to depart".

In a fascinating experiment, expert airline pilots were asked to prepare rules for novice pilots. The novice pilots followed the rules and had no problems with them. However, when the expert pilots were then asked to follow their own rules, they found that their performance fell sharply. This is because expert pilots do not usually fly planes the way described in the rules. Expert pilots rely a lot on experience and intuition and often break the very rules that they had prescribed. They use contextual decision making and rules leave very little room for this type of decision making. However, had novice pilots been asked to perform without the rules, they would not have been able to, because they lacked the experience and intuition. Rules are critical for novice pilots to fly a plane. That is Shu Ha Ri. What is good for the expert is often not so good for the novice and vice-versa.

This principle is particularly applicable to process, or software development process to be more precise, although it is equally applicable to any organizational process. The great big battle about whether we need processes or not is missing the point completely. Everyone follows a process in their head. Even no process is a process. The question is whether to follow a predefined process or an ad-hoc process where you just do whatever you are thinking of at that moment.

Let us apply the Shu-Ha-Ri principle at this point. Are you a novice at managing projects? In that case you need a clear, unambiguous process. If you have been in multiple project, then you need a less defined process, or apply your own process if you are an expert at project management. These leave room for the contextual decision making we talked about earlier. However, the reverse will simply not work. Leaving novices without a process, or imposing a rigid process on an expert are both doomed to fail right from the start.

So the point to take away from this is that the way novices and experts perform the same task is very different, and the guidance that they require is also very different. For all those grappling with the process question, think back again to Shu Ha Ri and see how it can help you.

See also: Dreyfus model of Skill Acquisition

This post is a part of the selected archive.

Flower with raindrops

Flower
Originally uploaded by Siddhi.

Took this photo yesterday at the Singapore Botanical Gardens. It had just finished raining when I took this shot with the raindrops still on the petals.

Opera targetting new devices

Opera has slowly moved from writing browsers for mobile phones to writing browsers for every sort of device. A few months ago, Opera announced a browser for the Nintendo DS, a handheld video game platform. Yesterday, Opera announced support for the Opera browser on Nintendo's upcoming Nintendo Wii console. To quote Eskil Sivertsen:

"More and more devices are featuring the Opera browser. From PCs to mobile phones, in-flight entertainment systems, media players and game consols. The browser is becoming a central application on these devices, bringing truth to our mission of offering the best Internet experience on any device."

Holy cow

[via Manu] When I read this, I was like.. Holy Cow! A guy who caught the Assistant Commissioner of Police (!!) run a red light.

I caught up with him a few hundred metres later, and pulled up beside the officer’s window. I looked in, and I caught his eye. I asked him (quite politely, I may add) what a guy like me is expected to do when I see an officer in uniform, on duty, violate a rule the way he just did. From his reaction, I judge that no one had ever asked him this question earlier.

What should a PM do when the project is late?

So, let us say that you are the project manager for a project. The delivery date is in a weeks time and you know pretty well that you will not make the date. What do you do? Think about this for a while.

Here is what should be done

1. Inform the client that you will not be able to make the delivery date and reschedule it for later.
2. Remove any roadblocks that are slowing down the development team (this should be done always, not just when the team is behind schedule).

Sounds pretty simple? Yet, most PMs don't do this. Why? Because owning up to the client is hard. It's a lot easier to imagine that some miracle is going to occur and the team will make the date. But of course, what will happen is that the team won't make the date and you'll have to inform the client anyway - on the day of the delivery.

PMs also worry a lot about meeting the schedule, but they don't write code, so they cannot change the team progress in any way. But they can help the team speed up. How? Remove roadblocks that affect the team. Yet, many times they are so busy worrying about the schedule that they do not think about the things that really affect the team.

I like think of PMs as outward-looking or inward-looking. Outward-looking PMs are looking at the schedule and pressurising the team, whereas inward-looking PMs are looking at the team and protecting the team. As an extreme, neither completely outward-looking, nor completely inward-looking PMs are desirable, because you need to satisfy both the customer and take care of the team. However, I find that most PMs are too outward-looking, to the detriment of the team.

This post is a part of the selected archive.

Recursion Part 4: Tree Recursion and Dynamic Programming

The following is a part of a series of articles I had written on recursion.

---

This part introduces tree recursion, a form of recursion that occurs when a function calls itself more than once in a path. We then introduce dynamic programming, a class of algorithms to tackle certain types of tree recursive problems.

All Parts:

Recursion Part 1: Introduction to recursion
Recursion Part 2: Tail recursion, Accumulators and Iteration
Recursion Part 3: Exercises in tail recursion
Recursion Part 4: Tree Recursion and Dynamic Programming
Recursion Part 5: Structural and Generative Recursion
Recursion Part 6: References and Further Information

---

Some recursive functions call themselves more than once. Consider the function to calculate the n^th term of a fibonacci series:

int fibonacci(int n)
{
    if (0 == n) {
        return 0;
    } else if (1 == n) {
        return 1;
    } else {
        return fibonacci(n - 2) + fibonacci(n - 1);
    }
}

In order to calculate fibonacci(4), we need to calculate fibonacci(2) and fibonacci(3). For each call, there are two more recursive calls. This proceeds until n becomes 0 or 1, which are the terminating points of the recursion. We see that execution follows a tree form like this:

fibonacci(4)
   +------------------------------
   |                             |
fibonacci(2)                 fibonacci(3)
   +-----------------            +---------------
   |                |            |              |
fibonacci(0)   fibonacci(1)  fibonacci(1)  fibonacci(2)
                                                +-----------
                                                |          |
                                           fibonacci(0) fibonacci(1)

Each node has two children, one for each recursive call. A function with 'n' recursive calls will have 'n' children at each node. Since program execution follows a tree like structure, we call this form of recursion tree recursion

Is there any way to convert tree recursion to iteration?

The short answer is no¹. There is no general algorithm to convert tree recursion to iteration. However, specialised algorithms do exists for certain problems. These algorithms (if they exist) are usually specific to each problem.

And it just so happens that our fibonacci algorithm falls into a class of tree recursive problems that can be converted to iteration using a technique called dynamic programming!

Look at the execution pattern for fibonacci(4) again. Notice how fibonacci(2) is calculated twice: Once in the computation of fibonacci(4) and once again in the computation of fibonacci(3). fibonacci(1) is computed thrice!

What if we could save the values of previous fibonacci terms when they are first computed and reuse the values later on without having to compute them again? This optimisation is the cornerstone of dynamic programming.

Here is how we can proceed:
1. Store the initial values of fibonacci(0) and fibonacci(1)
2. Compute fibonacci(2) from fibonacci(0) and fibonacci(1). The saved value of fibonacci(0) is now no longer required, so we can discard it.
2a. In general, compute fibonacci(n + 1) from the saved values of fibonacci(n - 1) and fibonacci(n). Discard the value of fibonacci(n - 1).
4. Repeat step 2a until we have computed the desired term

Look at the execution tree again. Notice how we start the computation from the leaf nodes of the tree and work our way up the tree computing each node, until we reach the root, which is the value we desire.

Here is the implementation using iteration:

int fibonacci(int n)
{
    int a = 0, b = 1, temp = 0;
    int i = 0;

    for (i=1; i<=n; i++) {
        temp = a + b;
        a = b;
        b = temp;
    }
    return a;
}

We have just used dynamic programming to convert a tree recursive algorithm into an iterative algorithm. The basic idea of dynamic programming is to look at the execution tree, identify repeated computations and perform the calculations 'bottom-up' from leaf to root. At each step, the computed values of the subproblems are stored to be reused later.

Dynamic programming cannot be used on every problem. Some problems can be converted to iteration using other methods, and some problems cannot be converted to iteration at all. Nevertheless, dynamic programming works on a large class of problems, and it is a useful tool to have in the toolbox

---

¹ You can write an iterative loop that manages it's own stack, but that is basically equivalent to recursion.

---

Any questions? Comments? Please leave a comment using the comment form below.

This post is a part of the selected archive.

Agile India 2006

So the Agile India 2006 conference is around the corner once again. Too bad I'll be in Singapore when it happens.

Going through the list of topics once, I'm struck by a sense of deja vu. Yet another introduction to Agile. Yet more introductions to developer testing. Didn't we go through much of this last time?

And, how many sessions on tools!! Selenium, Watir, Frenkenstein, J2EE Testing, Sahi.. please, enough already! Last time it was FIT, Marathon, CppUnit, Cruisecontrol and DamageControl. Tool discussions should be limited to workshops. That's where they are the most useful. Nothing more boring than watch someone explain xml configuration files on a powerpoint slide.

Presentations should be for concepts: To illustrate, explaining why continuous integration is so damn cool should be done in a presentation. You want to generate people to buy in and believe in the concept. Describing a specific CI tool like Cruisecontrol or DamageControl should go into the workshop.

Two topics that caught my eye were "Design And Implementation of Robotics Languages" by Ravi Mohan and "Agile Approach to Bootstrapping a custom Firmware for Lego Mindstorms" by Rajesh Babu, just because they are so different from the rest.

I heard Ravi Mohan talk last year and it was very interesting for its "geek" factor. It was about using Agile techniques with AI software (using a combination of Lisp, Erlang, C and Ruby :) ). And then ripped up a few people on the panel discussion.. that was fun. We had a chat later on. His website is One Man Hacking.

The two keynotes also sound interesting, especially the one on DSDM. Most people equate Agile to XP, or sometimes Scrum. The fact is that there are many agile methods, some of which differ drastically from XP. From what I've read, DSDM is one of those. For instance, DSDM teams have specialist roles, whereas XP says that most team members should be cross-functional. And DSDM does emphasise some modelling, unlike the XP mantra of No Big Design Up Front.

A couple of people I'd really like to hear are Alistair Cockburn and David Anderson, (both are Scots incidentally) simply because they bring in such a different perspective on Agile. I'm a BIG fan of both of them. [Sometimes I think that the term Agile has been co-opted by the XP and Scrum groups, but that's a topic for another post.]

There are a few other interesting sessions here and there, but I just get this nagging feeling in my gut that most of the other sessions are just going to rehash the same old stuff yet again.

Anyway, for Rs.500, the conference is an absolute steal! Definately worth going to. It was excellently organised last year and certainly worth going to again this year. If you haven't registered yet, hurry up and register already. You can register online, and you only have to pay at the counter when you get there. The registration form is here.

This post is a part of the selected archive.

Recursion Part 3: Exercises in tail recursion

The following is a part of a series of articles I had written on recursion.

---

This part provides some exercises related to the concepts introduced in the previous part.

All Parts:

Recursion Part 1: Introduction to recursion
Recursion Part 2: Tail recursion, Accumulators and Iteration
Recursion Part 3: Exercises in tail recursion
Recursion Part 4: Tree Recursion and Dynamic Programming
Recursion Part 5: Structural and Generative Recursion
Recursion Part 6: References and Further Information

---

Try out the following problems: Ask any questions/answers in the comments.

Is this tail recursion?

int fibonacci(int n)
{
    if (n <= 2) {
        return 1;
    } else {
        return fibonacci(n - 2) + fibonacci(n - 1);
    }
}

What about this?

node findRoot(node child)
{
    if (NULL == child->parent) {
        return child;
    } else {
        findRoot(child->parent);
    }
}

And this?

node findNodeInList(node head, int dataToFind)
{
    if (NULL == head) {
        return NULL;
    } else if (head->data == dataToFind) {
        return head;
    } else {
        return findNodeInList(head->next);
    }
}

---

Try converting the above three programs to iterative versions. Do you find some harder than the others?

---

Convert this iterative program into a tail recursive version. First convert it to an accumulator based function and then convert that to an ordinary tail recursive version. Hint: First convert the for loop into a while loop.

int sumOfFirstNnumbers(int n)
{
    int i = 0, sum = 0;

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

How about this one? Assume all numbers are positive (> 0). Hint: The accumulator does not always have to perform some mathematical operation. It can also be used to keep track of the state so far.

int findMax(int *numberArray, int arrayLength)
{
    int i = 0, max = 0;

    for (i=0; i<arrayLength; i++) {
        if (max < numberArray[i]) {
            max = numberArray[i];
        }
    }
    return max;
}

---

Any questions? Comments? Please leave a comment using the comment form below.

This post is a part of the selected archive.

J2ME notes

Some J2ME notes :

1. Antenna : Ant tasks for building and packaging J2ME midlets
2. J2ME performance tips
3. Remember to catch those OutOfMemoryExceptions! It is all too easy to run out of memory on a contrained device and programmers used to writing code for PCs or servers are just not in the habit of handling out of memory errors

Recursion Part 2: Tail recursion, Accumulators and Iteration

The following is a part of a series of articles I had written on recursion.

---

This article introduces an important concept in recursion: the tail recursion. We see what tail recursion is, and where it is used. We end the article with the relationship between tail recursion and iteration.

All Parts:

Recursion Part 1: Introduction to recursion
Recursion Part 2: Tail recursion, Accumulators and Iteration
Recursion Part 3: Exercises in tail recursion
Recursion Part 4: Tree Recursion and Dynamic Programming
Recursion Part 5: Structural and Generative Recursion
Recursion Part 6: References and Further Information

---

Let us get back to the factorial program:

int factorial(int n)
{
    if (0 == n) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

As we saw in Part 1, the execution of this program goes like this:

factorial(4)
4 * factorial(3)
4 * 3 * factorial(2)
4 * 3 * 2 * factorial(1)
4 * 3 * 2 * 1 * factorial(0)
4 * 3 * 2 * 1 * 1
4 * 3 * 2 * 1
4 * 3 * 2
4 * 6
return 24

In this program, the multiplication with 'n' is the deferred operation (See Part 1 of this series for an introduction on deferred operations). Apart from the deferred operation, there is the recursive call to calculate factorial(n - 1).

Since the recursive call is the last step of the function, this type of recursion is called tail recursion. The name derives from the fact that the recursive call occurs at the end of the function. Oridinary tail recursion has a deferred operation and a recursive call. Pure tail recursion has no deferred operation, it only has a recursive call. The above implementation of the factorial is ordinary tail recursion because it has a deferred operation.

As we saw in Part 1, the deferred operation is carried out when the stack gets popped. Is there any way we can carry out the operation immediately and pass in the value to the function? Take a look at this implementation of factorial:

int factorial(int n)
{
    return factorial_acc(1, n);
}

int factorial_acc(int acc, int n)
{
    if (0 == n) {
        return acc;
    } else {
        return factorial_acc(n * acc, n - 1);
    }
}

Let us trace the execution of this program to calculate factorial(4):

factorial(4)
factorial_acc(1, 4)
factorial_acc(4, 3)
factorial_acc(12, 2)
factorial_acc(24, 1)
factorial_acc(24, 0)
return 24

Notice the difference with the normal factorial implementation? In this version, there are no deferred operations. Instead, the value of the deferred operation is calculated immediately and passed as the first parameter to the recursive function. This parameter is known as the accumulator parameter (in case you were wondering, that is why it is called acc, and the function is called factorial_acc). The role of the accumulator parameter is to accumulate the result of the operations at each step. Note that this version computes the multiplication during a stack push rather than a stack pop. Nothing is done during stack pop, and so this version is pure tail recursion.

Take a look at this iterative implementation of a factorial:

int factorial_iter(int n)
{
    int fact = 1, i = n;

    while (i > 0) {
        fact = fact * i;
        i--;
    }
    return fact;
}

Notice any similarities with the accumulator version? Look at how the variables change with each iteration while calculating factorial(4):

factorial_iter(4)
fact = 1, i = 4
fact = 4, i = 3
fact = 12, i = 2
fact = 24, i = 1
fact = 24, i = 0
return 24

Compare the fact and i variables in the iterative version with the acc and n parameters in the accumulator version. They are identical! In other words, the accumulator version simply implements a while loop using recursion!

So here is the big result: Any ordinary tail recursive program can be converted to a pure tail recursive program with accumulator, which in turn can be converted to a while loop. Thus, ordinary tail recursion and iteration are equivalent, and the above steps give us a way to convert between the two forms!

Because iteration is nothing but a special case of recursion, some languages like Lisp, Scheme and others do not have any iteration methods. There are no for loops, while loops or do-while loops in these languages. All looping is accomplished by using either ordinary or pure tail recursion! These languages have special mechanisms for optimising tail recursion so that they do not increase the stack size.

Languages like C include iterative methods and offer no special support for tail recursion. Since tail recursion is exactly equivalent to iteration, it makes sense to convert all tail recursion into iteration. However, beware of trying to convert non-tail recursion into iteration. As we shall see in later articles in this series, non-tail recursion is a very different beast altogether.

---

Any questions? Comments? Please leave a comment using the comment form below.

This post is a part of the selected archive.