Choosing a scripting language

CIO magazine has an article titled You Used THAT Programming Language to Write WHAT? They took five "scripting" languages — Ruby, Python, Javascript, PHP and Perl — and then get Zed Shaw, Martin Aspeli, Michael Morrison, Kenneth Hess and James Turner to write about what kind of applications the language is good for, and where you are better using another language. Check it out.

Screencast: Using Amazon S3 with Django

Many thanks to Balaji and CSS for organising the second Amazon Web Services meet in Chennai and to Jinesh for being able to make it. (Also check out my live blog of the event on twitter, starting here)

As a part of this meet, I had prepared a demo showing how to build a simple gallery application using Django and Amazon's S3 service. I've recorded it as a screencast and uploaded it on ShowMeDo. It's really simple to use S3 with Django, so take a look.

This screencast uses the Boto python library for accessing AWS.

Get the Flash Player to see this movie.

This video originally comes from here at ShowMeDo from the Python category.

Has Django reached the tipping point?

Antonio Cangiano thinks so. The numbers used to come to this conclusion are not exactly scientific, but there's no doubt that Django is getting bigger (and better) everyday.

Django Screencasts

A few people have been asking for introductory Python + Django material, so I thought I'd just link up to the two intro screencasts that I did for Django.

Learn Django: Create a Wiki in 20 minutes

This is a beginners screencast that assumes no previous knowledge of Django. We illustrate the basics of creating a web app in Django by developing a simple wiki application.

Learn Django: Extending the wiki with wikiwords and search

Following on where the first screencast left off, this screencast introduces some more django features such as template inheritance, filters and newforms library.

Using python to teach kids programming

Horst Jens uses Python to teach kids how to program at Profikids in Vienna. In the following screencast, we see one of the kids, Leo, program a simple GUI button box. The screencast is in German, but it has English subtitles. Check it out below -

Get the Flash Player to see this movie.

This video originally comes from here at ShowMeDo from the Python category.

Django screencast: Template inheritance, filters and newforms

Following up on my first Django screencast, I've put up the second screencast in the Learn Django series. Like the first one, its hosted on showmedo.com and you can view the screencast here.

The second screencast extends the wiki application we built in the first part by adding a menu, support for auto-linking of wikiwords and a feature to search through the database. In the process, you'll learn about some cool Django features such as template inheritance, custom filter libraries and Django newforms. Django newforms in particular is a very cool form handling library that can really cut down on boilerplate form generation and validation code.

Interested? Check out the screencast.

Generating sentences using Markov chains

So, a bunch of us - Aswin, Kausik, Moyeen, Sagaro - got together at Aswin's house on Sunday to have a python codekata. We did an intro to Python session, and we wrote a program to generate sentences using Markov chains.

I really like this program. Not only is it interesting to write and run but it makes for a very nice language intro. I'll be doing this session again as a workshop at Bangalore BarCamp 4 at the end of this month.

The final version of the program is given below. The example below uses sample text from Alice in Wonderland, downloaded from Project Gutenberg. Remember that this is the final version — In the actual kata, a number of variations were written before arriving here.

import random

def getLines(filename):
 return [line[0:-1] for line in open(filename).readlines()]

def getWords(lines):
 words = []
 for line in lines:
  words.extend(line.split())
 return words

def createProbabilityHash(words):
 numWords = len(words)
 wordCount = {}
 for word in words:
  if wordCount.has_key(word):
   wordCount[word] += 1
  else:
   wordCount[word] = 1
 
 for word in wordCount.keys():
  wordCount[word] /= 1.0 * numWords
 return wordCount

def getRandomWord(wordCount):
 randomValue = random.random()
 cumulative = 0.0
 for word in wordCount:
  cumulative += wordCount[word]
  if cumulative > randomValue:
   return word

# replace with a large text sample. Here we are using Alice in Wonderland
# from Project Gutenberg
words = getWords(getLines("alice.txt"))

wordMap = {}
previous = (words[0], words[1])
for word in words[2:]:
 if wordMap.has_key(previous):
  wordMap[previous].append(word)
 else:
  wordMap[previous] = [word]
 previous = (previous[1], word)

for word in wordMap.keys():
 probabilityHash = createProbabilityHash(wordMap[word])
 wordMap[word] = probabilityHash

previous = ("The", "next") # The starting words
numWords = 100 # The number of words to print

print previous[0], previous[1],
for i in range(numWords):
 word = getRandomWord(wordMap[previous])
 print word,
 if word.endswith("."):
  print "\n"
 previous = (previous[1], word)

Erlang demo video

Harish Mallipedi has a very nice post pointing to an interesting erlang demo video.

This is probably the only time I have seen someone demo their programming language by making phone calls to each other. It is fun! Watch it.

Check it out!

Code coverage for your Django code

One of the things that I like about Django is that it allows you to run unit tests on the code with relative ease. So I have a bunch of unit tests now, and I was looking to expand it. For that I first needed to know which parts of the code had good coverage and which parts had no coverage. I needed to integrate code coverage with the unit testing framework. In the end, it involved modifying a few files. This is what I did:

1. First, I downloaded Ned Batchelder's coverage.py module.
2. Next, get this script to colorize the coverage output. I saved it as coverage_color.py
3. Put both files somewhere on the python path. I put it at Python24\Lib\site-packages
4. Now we need to modify the django unit test runner to include coverage. Head over to your django\test directory and edit the simple.py file
5. At the top, add the following line:

   import os, coverage, coverage_color

6. Scroll down to the run_tests function. You will see a line like this:

       unittest.TextTestRunner(verbosity=verbosity).run(suite)
       destroy_test_db(old_name, verbosity)

7. Modify it to read like this:

       coverage.start()
       unittest.TextTestRunner(verbosity=verbosity).run(suite)
       coverage.stop()
       if not os.path.exists(settings.COVERAGE_DIR):
           os.makedirs(settings.COVERAGE_DIR)
       for module_string in settings.COVERAGE_MODULES:
           module = __import__(module_string, globals(), locals(), [""])
           f,s,m,mf = coverage.analysis(module)
           fp = file(os.path.join(settings.COVERAGE_DIR, module_string + ".html"), "wb")
           coverage_color.colorize_file(f, outstream=fp, not_covered=mf)
           fp.close()
       coverage.erase()
       destroy_test_db(old_name, verbosity)

8. What that does is to record the coverage when running the tests. It then creates a directory for putting the HTML output, creates the colorized version of the source and dumps it into the output directory. At the end of everything, it cleans up the coverage data
9. We now need to configure the COVERAGE_DIR and COVERAGE_MODULES settings. Open your Django settings.py file and add the following lines:

   COVERAGE_DIR = "scripts/build/coverage" # Where the HTML output should go
   COVERAGE_MODULES = ["apps.catalyst.views", "apps.catalyst.models"] # The modules that you want colorized

10. Save and run your Django unit tests. After running, you will have a html file for each module in the specified directory with the colorized coverage output

Check out the output: The lines in red were not executed by any of the unit tests. Looks like there is a function that I'm not testing at all!

Django screencast: Create a wiki in 15 minutes

I've uploaded a screencast on how to write a wiki in 15 mins with Django. Its available on the Silver Stripe Blog here.

Can your programmers read code?

Surprising as it might seem, programmers spend a majority of the time reading code, not writing code. Take my case. Even though I am working alone, on a new project, I spend the majority of my time reading code. That's not just my code, but also the code in the various open source modules that I'm using. At some point or the other, I've had to delve headlong into the source of Django, Dojo, Mochikit and ToofPy, and try to make out what the code is doing by ignoring the docs (if there are any!) and reading the source. If you are working in a team, the effect is magnified even more.

This was no sudden revelation. When I was hiring, I had a standard question to see if candidates could read code. Here is the code snippet.

int function f(somestruct *a) {
    int x = 0;
    if (NULL == a) {
        return 0;
    }
    x += f(a->left);
    x += 1;
    x += f(a->right);
    return x;
}

Candidates had to try to figure out what function f was doing.

First, I expected the candidate to see the left and right fields and guess that "a" was a pointer to a binary tree of some sort. I then expected the candidate to see the pattern of the recursive calls and guess that it was a tree traversal (inorder in this case). Once that's done, its simple to try out the function with some data and figure out what it does (count the number of nodes).

Given that everyone learns about binary trees, and especially inorder traversal, you would have expected many to get it right. Surprise! Only a few have ever got it correct.

Most answers were something related to linked lists or arrays. It seemed that every programmer when confronted with a pointer in any form assumed it was related to linked lists!!

To be successful at code reading, it is the ability to execute the program in our mind that needs to be developed. This is a learned skill, developed by just reading lots of code.

One conclusion is that many programmers don't spend enough time reading code. It also explains why in many teams, most code becomes spaghetti — programmers can't read the original code, so they hack their fixes.

So, do you check to see if programmers can read code? As an aside, you can now find out how most programmers can't write code either.

Using python decorators to implement guards

One cool technique that I learnt while going through the Django code was using python decorators to implement guards.

What are guards?

Take a look at this bit of pseudo-code

if condition1:
  if condition2:
    {do_something}
  else:
    return error2
else:
  return error1

This is a common pattern where you do something provided condition1 and condition2 are false. The problem with this code is that it is difficult to seperate out the core logic of the function contained in {do_something} and the error handling code in the rest of the function. Another disadvantage is that the condition is at the top of the function, while the failure action is at the bottom. This makes it difficult to correlate the condition with the failure action.

The solution is to refactor the code to use guards.

if not condition1:
  return error1

if not contidion2:
  return error2

{do_something}

Guards are the conditions at the top of the function. They act like security guards — If the condition passes you go through, otherwise you leave the function. It is now a lot easier to see the conditions and the failure actions, and you can easily identify the code logic block by just skipping past the guards.

Python decorators

Python has a decorator feature that allows you to modify the function that it is applied to. Here is an example:

def decorate(fn):
  def _decorate():
    print "before calling"
    fn()
    print "after calling"
  return _decorate

@decorate
def myfunction():
  print "in function"

What we have is a function myfunction that prints the string "in function". To this, we apply the decorator 'decorate' (denoted by the @ symbol). decorate is itself a function that takes one function as a parameter and returns another function. In this case, it takes fn as a parameter and returns _decorate. Everytime myfunction is called, it will actually call the returned function, in this case _decorate. _decorate prints "before calling", then it calls the original function, then prints "after calling". Here is the output

>>> myfunction()
before calling
in function
after calling

Implementing guards using decorators

We can now see how guards can be implemented using decorators. Let me take a real example that I've encountered — my admin page. My tool has an admin page. In order to access this page, you must be logged in, and you must be an admin. If you are not logged in, you need to be redirected to the login page. If you are not an admin, an error message should be displayed. This is how the code would normally have looked

# check for login
try:
  user = request.session["user"]
except KeyError:
  # redirect user to login page

# check for admin
if not user.isAdmin():
  # display error page

# show admin page
...

Here is a version using decorators

# login decorator checks whether the user is logged in
def login_required(fn):
  def _check(request, *args, **kwargs):
    try:
      user = request.session["user"]
    except KeyError:
      # redirect to login page
    # user is logged in, call the function
    return fn(args, kwargs)
  return _check

# admin decorator checks whether the user is an admin
def admin_required(fn):
  def _check(request, *args, **kwargs):
    user = request.session["user"]
    if not user.isAdmin():
      # return the error page
    # user is admin, call the function
    return fn(args, kwargs)
  return _check

@login_required
@admin_required
def admin(request):
  # show admin page
  ...

This is how it works. We first have the admin function. All it does is implement the admin code. We decorate it with the admin_required and login_required decorators. When the admin function is called, it first enters the login_required decorator function which checks for login. If the user is not logged in, it redirects to the login page, else it calls the function. The function passed to login_required is the admin_required decorated function. So if login passes, it calls the admin_required decorator, checks for admin. If the user is not an admin, it displays an error message, else calls the function, which in this case is the original admin function.

See how neatly the guards are separated from the core logic. The admin function contains only the core logic, while the list of guards is neatly arranged as decorators. This method also has another advantage — it is easy to apply the same guards to other functions. Take a look at this

# no decorators
def login(request):
  ...

@login_required
@admin_required
def admin(request):
  ...

@login_required
def dashboard(request):
  ...

@login_required
@project_permission_required
def view_project(request, project):
  ...

Now each function only implements the core logic, while all the guard logic is taken care of by the decorators. It is easy to see the core logic and easy to see the guard conditions applied for the function. If I want some other function to have a guard, I can just add a decorator to it without touching the core logic. Best of all, the code is self descriptive and very easy to read.

This post is a part of the selected archive.

Rapid Web App Development — My experiences while developing Catalyst

My talk at the barcamp was titled "Rapid Web App Development — My experiences while developing Catalyst". Catayst is the name of my project management tool. The presentation was created using a modified version of Eric Meyer's S5 presentation tool. The template allows you to create the presentation content in XHTML and style it using CSS. It's really awesome, and I feel a lot more comfortable with it than Powerpoint or OpenOffice. However, there is no place to upload it. Another problem of putting the slides online is that it lacks the voice over and discussion that actually took place. Since the slides by themselves are pretty meaningless, I've added some commentary below.

---

The goal: Write a web application with one person, one month of work to get to version one. That's what I'm trying to do with Catalyst. I've spent about 80 hours working part time on Catalyst. At that time, it was only a hobby project for me to learn Django, and AJAX. I've worked about 100 hours on it full time since I returned to India. I'm hoping to get to beta before the end of the year.

Catalyst is a project management tool for small, agile and distributed teams. If you have ever been frustrated with the lack of visibility into what everyone else is doing in the project, especially with multiple offices, then Catalyst is for you. But this presentation is not about Catalyst. It is about what I have learnt while attempting to develop an application in a month.

There are six points that I want to discuss, split into two areas. The first area is the philosophy, and the first point is that constraints are good.

The more constraints one imposes, the more one frees one's self. And the arbitrariness of the constraint serves only to obtain precision of execution — Igor Stravinsky

Most of us think of constraints as bad, something that limits our freedom, but constraints can be good. Take the example of the one month limit, an arbitrary constraint. Why develop version 1 in a month? Why not six months or a year? I could have chosen a year and done a lot more features, but the one month constraint forces me to select the most important features and implement them first. In this case, the constraint helps me to focus on what is essential. Constraints can also drive innovation and spur creativity.

Second is the 'less is more' philosophy. There are two angles to this. The first is that the fewer requirements you have, the less you have to design, code and test. In that sense, it obviously help you finish faster and get the product out. The other way of looking at it is simplicity. If you look at Catalyst, it does not have an integrated bug tracking system like many project management systems. Why? By eliminating bug tracking from the list of features, I retain the focus on project management. Not only does it simplify Catalyst, but the users can continue to use their favourite bug tracking tool. In my opinion, this combination is actually worth more than having integrated bug tracking within Catalyst.

The second area I want to focus on is execution. This is the actual development part. How do you speed it up? My favourite is the combination of expressive languages and powerful frameworks. Catalyst is written in python and django. Here is an example: In the project dashboard screen, we need to get all the tasks that are a part of the interation that is currently in progress. The python code to do this is just six lines, with no SQL to be written!

The fifth point is to do smart testing.

There are two ways to write error-free programs; only the third works. — Alan Perlis

You'll never write error free code and since there is only one person, you have to rely on automated tests. Javascript code is unit tested using jsUnit. I am looking to start using the Django extensions to python's unittest module for testing the server side code. Another tool I want to learn is Selenium for automated system tests. Of course manual tests have their place too. I am using catalyst to manage my development work, so that kind of dogfooding helps in areas like usability and finding bugs via basic exploratory testing.

Finally, use libraries! The less code you have to write, the easier it is. Catalyst uses Dojo and Mochikit on the client side. Dojo has a bunch of widgets that really ease development, while Mochikit has a really cool DOM creation API. Catalyst uses both. PIL is used on the server side to generate charts. Apart from this, a lot of repeated code has been refactored into libraries. This is general good practise of course, but its often not done. See how the constraints force you to develop better?

To summarise, here are the six points again

1. Constraints are good
2. Less is more
3. Expressive languages
4. Powerful frameworks
5. Smart testing
6. Libraries

Export django database to an xml file

Here is a simple python script to export your django database to an XML file. I haven't tested it out very thoroughly. It seems to work for the fields that I have in my model - CharField, TextField, DateField, IntegerField, PositiveIntegerField and ForeignKey. If you find any bugs, add a comment to this post.

# setup the environment
import os, sys
sys.path.append(os.pardir)
os.environ["DJANGO_SETTINGS_MODULE"] = "settings"

class XMLWriter:
    """Helper class to write out an xml file"""
    def __init__(self, pretty=True):
        """Set pretty to True if you want an indented XML file"""
        self.output = ""
        self.stack = []
        self.pretty = pretty
        
    def open(self, tag):
        """Add an open tag"""
        self.stack.append(tag)
        if self.pretty:
            self.output += "  "*(len(self.stack) - 1);
        self.output += "<" + tag + ">"
        if self.pretty:
            self.output += "\n"
        
    def close(self):
        """Close the innermost tag"""
        if self.pretty:
            self.output += "\n" + "  "*(len(self.stack) - 1);
        tag = self.stack.pop()
        self.output += "</" + tag + ">"
        if self.pretty:
            self.output += "\n"
        
    def closeAll(self):
        """Close all open tags"""
        while len(self.stack) > 0:
            self.close()
        
    def content(self, text):
        """Add some content"""
        if self.pretty:
            self.output += "  "*len(self.stack);
        self.output += str(text)

    def save(self, filename):
        """Save the data to a file"""
        self.closeAll()
        fp = open(filename, "w")
        fp.write(self.output)
        fp.close()

import django.db.models

writer = XMLWriter(pretty=False)
writer.open("djangoexport")
models = django.db.models.get_models()
for model in models:
    # model._meta.object_name holds the name of the model
    writer.open(model._meta.object_name + "s")
    for item in model.objects.all():
        writer.open(model._meta.object_name)
        for field in item._meta.fields:
            writer.open(field.name)
            value = getattr(item, field.name)
            if value != None:
                if isinstance(value, django.db.models.base.Model):
                    # This field is a foreign key, so save the primary key
                    # of the referring object
                    pk_name = value._meta.pk.name
                    pk_value = getattr(value, pk_name)
                    writer.content(pk_value)
                else:
                    writer.content(value)
            writer.close()
        writer.close()
    writer.close()
writer.close()
writer.save("export.xml")

Note to self: Find a better way to colorize the source code

This post is a part of the selected archive.

On web frameworks and AJAX

I recently started working on a new project at home. Its a web application to help out with project management. The two goals were 1) to develop something that I could use for the projects at work and 2) to learn something new. This project was perfect for learning something that I had always wanted to learn more about: Web frameworks and AJAX - both hot areas of Web 2.0 (and yes, although there is a lot of hype around Web 2.0, it is clear that a new web revolution is underway, and it is not just a passing fad).

Given a choice, I prefer to work in Python, so I went around looking for web frameworks in Python (and there are a LOT of them). I finally decided upon django, having heard a lot of good things about it (the fantastic website also helped).

Having worked a bit with it, I can now say WOW. The basic framework for the site is already done and it only took two full days and two nights to get it here. Further, one of the full days was dedicated to designing the look and style of the site, so only a day and two nights were spent on programming. This includes a complete and customised administration area where you can modify any object in the system. Sure, there is still a lot to do, but to still get this far in such a short time has been amazing.

I'm now looking to refine the interface, and that means AJAX. I'm currently looking into the Dojo and Mochikit libraries. I've implemented my first drag and drop using Dojo and in-place editing with Mochikit. That has taken another day. I currently like Mochikit as it is much easier for the beginner to get started with. Dojo looks a lot richer, but its really hard to learn with very scant documentation. Of course, my lack of experience with Javascript (and especially the way OO is done in Javascript) and my familiarity with Python (which Mochikit tries to emulate) may have something to do with that.

After this preliminary experiment, I can say with some confidence that a single person working full time on an application can get a first version out within a month. Capital and resources are no longer major problems. All you need is a good idea. In other words, the next few years will be a great time to be an entrepreneur, much like the years in the late 90s.

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.

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.

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.

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.