Archives: July 2011

Understanding recursion

Recursion is something a lot of people find hard, even mystical. I learned to understand it, and even like it quite a bit, by learning Lisp. Recursion lets you solve problems in very elegant ways, and when you understand it, it will be really natural to you.

But the question is, how do you learn it? No, not just learn to know what it is, but really understand it. There is no magical formula which I have found, it just takes practice. As I said, learning Lisp taught me how to understand recursion. The reason was simply that Lisp more or less forces, or at least encourages, you to use recursion for solving many problems and thus forcing one to practice it.

What is recursion, really?

To solve problems using recursion, you want to have a function call itself, and for each call, solve a smaller problem than the initial problem in order to finally solve the big one. Take a simple example, a function for calculating the sum of all natural numbers up to some value of n (the example is in Java):

public static int sumTo(int n){
  if(n==1){
    return 1;
  }else{
    return n + sumTo(n-1);
  }
}

We could call this function, for instance by typing sumTo(5);. A smaller problem would be the sum of all natural numbers up to 4, or 3, or 2, or just one. This is exactly what this recursive function does; it solves each of the smaller problems.

The sum of all natural numbers up to 1 is 1, and if n is 1, that gets returned by our function (this is called the base case, which every recursive function should have in order to properly finalize execution). The recursive call occurs at line 5. It returns n added to the sum of all natural numbers less than n, thus what we get is roughly:

//The following is called stack winding, which is when we go to the base case
sumTo(5);
  5 + sumTo(4);
    sumTo(4);
      4 + sumTo(3);
        sumTo(3);
          3 + sumTo(2);
            sumTo(2);
              2 + sumTo(1);
                sumTo(1);
                  //The following is called stack unwinding
                  1
              2 + 1 = 3
          3 + 3 = 6
      4 + 6 = 10
  5 + 10 = 15

The above is called a stack trace; they can be useful while starting out with recursion, but when you get experienced with recursion, you won’t need them any more (you will just trust it).

Why do you need recursion? Couldn’t you write the previous function using iteration instead of recursion, like:

public static int sumTo(int n){
  int i, sum=0;
  for(i=1;i<=n;i++){
    sum+=i;
  }
}

Yes, you could. It would probably be faster, too (depending on how the compiler optimizes the code). Yet, there are cases when iteration just won’t work to replace recursion, or where iteration is really, really clumsy or inelegant (on the contrary, recursion is almost always elegant). One problem where recursion is (definitely) superior to iteration is the task of walking through all the directories in a filesystem. Say that we want to print every file on a filesystem, we would do it the following way:

walkthrough(file):
  print name of <file>
  if(<file> is directory):
    for files in <file>:
      walkthrough(files)

The first file would be the root directory, containing all other files and directories. For each file (and directory) found, the name is printed. If we find out that that the file is a directory, we go through its children (subfolders and files) and then, for each of them, we call the function itself, printing the name of each of the children and if any of the children are directories themselves, walkthrough() is called on them, printing their contents as well.

Practice (using Scheme)!

To learn recursion, you will need practice (I’m sorry, as I said, I have no magical formula). I would suggest you to learn Scheme, a minimalist dialect of Lisp. There is a famous computer science book for it, (available online for free), and some using the book (by the authors of the book).

Use Scheme to practice problems using recursion. You can of course use another language, but I would say that some dialect of Lisp would be the best place to learn recursion, as the language itself is very well-suited for solving problems that way.

Some problems that can be solved recursively include:

  • Calculating the factorial of n (n!)
  • Calculating the sum of values in a list
  • Calculating the n:th Fibonacci number
  • Calculating the greatest common divisor of two numbers using the Euclidean algorithm
  • Traversing directories (write a real solution, don’t use pseudocode as I did)

You can find more information on recursion at Wikipedia, as well as examples.

Beginner Programming Mistakes

Interested in programming? Great! Programming is lots of fun. You want to do things well though, even if its not that important while just learning. I will list some of the beginner mistakes I did myself here, and that I have seen others do, just so you can avoid them.

Focus too much on programming languages

Many times have I seen people just getting into programming wondering what programming language to learn. Read this: languages aren’t that important. A good learning language would be Python (which is good otherwise, too), but other languages are good as well. Now the thing that makes a programmer good isn’t what language a programmer uses, similar to how the language a poet writes in isn’t making the poet a good or bad poet.

Don’t just learn a programming language either, learn good programming practices. You can learn such from, for instance, the book .

Run straight into coding

Before writing even a line of code, plan how your application will work at a high-level on paper. I did this mistake many times, and I ended up throwing everything away and starting again because of that. How will your application solve a problem? Figure that out first.

Be too optimistic

Sure, we all want to create the next Google/Windows/World of Warcraft (I’m not so sure about Windows…), but that might be too much for a starter project. Google uses very complex algorithms (very complex things to make it work) to be able to find good results from the enormous web, operating systems, such as Windows, in general are complex and require a lot of detail knowledge about how computers work and complex games such as World of Warcraft aren’t easy at all, requiring lots of knowledge about heavy mathematics and physics.

I don’t want to scare you away, but don’t do it because you want to have that done. Sure, you might be working on things like that someday, but start small, and do it because you like doing it, and not for any other reason. How do you know if you like programming? Well, just try it out.

Also, a sidenote to all those interested in creating games; don’t learn C++ as a first language, it is very complex. You can create games in other languages too, even if the games industry doesn’t use them as much as C++. A good language is Python, and it provides something called PyGame, making game development a lot easier. If you are in for computer games, I would suggest the book Invent your own computer games with Python. Also, programming isn’t everything in the game world; if you aren’t great at mathematics, you might want to consider doing art for games or something else, because game development will have a lot of math.

Give up to early

Programming is hard and it takes a lot of time to get good at it. I have programmed for a few years, and I have a lot to learn. If you hit a stumbling block, don’t give up. Try to solve it. If you don’t like such stumbling blocks, you might not like programming, which, largely, is about problem solving.

Avoid challenges

Avoiding challenges is, to some extent, avoiding the ability to improve. Do projects that you know will be challenging. Do things that you aren’t sure how to do, and then learn how to do it by doing that. Practice makes perfect.

Skip the basics

You want a solid foundation. You won’t get a solid foundation by skipping the basics and moving directly to the “cool” stuff. I know, basics can be boring, but they are the foundation for good programming ability, and you don’t want to be a bad programmer, do you?

What this essentially means, you should know what “recursion” is before creating a graphical user interface.

The most useful GCC options and extensions

This post contains information about some of the most useful GCC options. It is meant for people new to GCC, but you should already know how to compile, link and the other basic things using GCC; this is no introduction. If you want an introductory tutorial to GCC, just .

The things this article attempts to cover include (as well as a few other things):

  • Optimization
  • Compiler warning options
  • GCC-specific extensions to C
  • Standards compliance
  • Options for debugging
  • Runtime checks (e.g. stack overflow protection)

For more information on GCC, the freely available An Introduction to GCC book is pretty good. A manual with over 700 pages is available as well (it’s a reference, not a tutorial, though) from the GCC website. The manpages for GCC (man gcc) can also be useful.

Basic compiler warning and error options

An option many programmers always use while compiling C programs is the -Wall option. It enables several compiler warnings not enabled by default, such as -Wformat warning at incorrect format strings. To enable even more warnings, use the -Wextra option. All warnings can be turned off with -w. More warnings will make catching eventual bugs easier, but it may also raise the amount of false-positives. The exact implications of these different options, as well as individual warnings can be found here.

To treat compiler warnings as errors, use the -Werror option. To stop compilation when the first error occurs, use -Wfatal-errors.

Standards compliance

By default, GCC may compile C code that is not necessary standards-compliant, or it might not even compile code that complies to the C standard (“the C standard” here means either C89 or C99). Some C standard features are disabled by default, such as trigraphs (can be enabled with -trigraphs), and several GCC extensions (will be talked about later on in this article) will work, even if they aren’t parts of the official C standard.

The -ansi option can be used to make GCC correctly compile any valid C89 program (if not, it is due to a compiler bug). It will still accept some GCC extensions (those that aren’t incompatible with the standard); use the -pedantic option to make GCC a pedant when it comes to standards compliance. The -std= option can be used to set the specific standard. There’s a bunch of supported standards (and most standards have several valid names), but the important ones to know are c89 (equal to the earlier -ansi option), c99, gnu89 (C89 with GCC extensions, which is the default) and gnu99 (C99 with GCC extensions). You can also use c1x to enable experimental support for the upcoming C1X standard (or gnu1x for the same with GCC extensions).

Code optimization levels

You can set the code optimization level for GCC, which decides how aggressively GCC will optimize the code. By default, GCC will try to compile fast, thus no optimizations will be made. By setting an optimization level, GCC will spend more time compiling, and the code might be harder to debug as well, but optimize the code better, possibly resulting in a faster executing program and/or smaller binary filesize. Because of longer compile-time and possible complications making debugging harder, it can be a good idea not to optimize during the development process and wait with that for building the production binary.

The default optimization(less) level is set with the -O0 option, or by giving no optimization option at all.

Some of the most common optimization forms can be activated by using the -O1 (or simply just -O) option. This option tries to produce smaller and faster binaries, and in many cases it can compile faster than -O0 because some optimizations will simplify the program for the compiler as well.

The next level is, perhaps unsurprisingly, -O2. It tries to improve the speed of programs even more than -O1 does, without increasing the size. It can take a much more considerable amount of time to compile. This is recommended for production releases as it optimizes well for speed without sacrificing space.

The -O3 level does some of the heaviest, most time consuming optimizations. It may also increase the size of the binary. In some cases, the optimizations may backfire and actually produce a slower binary.

If you want a small binary (most of all), you should use the -Os option.

Just pre-process, compile or assemble

When you ask GCC to compile a C program, the following steps are usually taken:

  1. Pre-processing
  2. Compilation
  3. Assembling
  4. Linking

For different reasons, you may want to stop at some of the steps. You might just want to pre-process, for instance, to find an error you suspect comes from a faulty pre-processor directive. If you do so, you will see the output from the pre-processor instead of getting the complete finished binary. Likewise, you may wish not to link because you are going to link manually later on, or maybe you just want to get the assembly output, modify that in some way and then manually assemble and link it. The reasons why you would want to do that isn’t the important thing here though, but how to do it.

To only pre-process, you should use the -E option. To stop after compilation, use -S. To do all steps but linking, use -c.

Controlling assembly output

Normally GCC produces AT&T syntax assembly output, but if you want to use Intel’s syntax (which is, in my opinion, much more readable), you should set the assembly dialect with the -masm= option, with intel as the value (-masm=intel). Note that this won’t work on Mac OS X.

A useful option for making the Assembly code more readable is the -fverbose-asm, which adds comments to the assembly output.

Adding debug information

If you are going to debug your program later, and don’t want to debug the assembly version, the -g option is absolutely essential. It adds debugging information, so that you can do source-level debugging later on the binary. The -g option produces debug information specifically for GDB, so what you get will not necessarily work on other debuggers.

You can set the level of debug information to generate. The default level is 2. With -g1 you can inform GCC to produce minimal debugging information, and with -g3 you can tell GCC that you want even more debug information than what you get by default.

Adding runtime checks

GCC can add different runtime checks to C programs at compilation, making debugging easier and avoiding some of the most common security vulnerabilities in C programs (as long as vulnerabilities/bugs don’t exist in the checking…). Note that runtime checks can degrade performance of programs.

There is an incredibly useful GCC option, -fmudflap, which can be used to find pointer arithmetic errors during runtime. This can help you find many pointer arithmetic related errors.

Stack overflow protection can be enabled by using -fstack-check.

The -gnato option enables checking for overflows during integer operations.

GCC extensions to the C language

GCC provides several extensions to the C programming language that aren’t actually parts of the C standard. You should always be careful while using non-standard features as that would, in most cases, make your code incompatible with other compilers. Anyway, I will cover some of the most useful extensions GCC provides, and you decide if you use them or not.

All extensions can be found in the GCC documentation.

Likely and unlikely cases

One GCC extension frequently used in the Linux kernel is the GCC extension __builtin_expect option, commonly known as the likely() and unlikely() macros. The Linux kernel would use something like the following for telling GCC which if statements are likely and unlikely to execute, so that GCC can do better branch prediction:

/*This is the likely case which will occur most of the time*/
if(likely(x>0)){
  return 1;
}
/*This is the unlikely case which will occur much more
 *seldom than the earlier case*/
if(unlikely(x<=0)){
  return 0;
}

The likely() and unlikely() macros are defined in the Linux kernel as:

#define likely(x)       __builtin_expect((x),1)
#define unlikely(x)     __builtin_expect((x),0)

If you want to use this outside the Linux kernel, you could always type __builtin_expect(condition, 1) for likely cases and __builtin_expect(condition, 0) for unlikely cases, but it would be much easier to use the same macros as the Linux kernel uses.

Additional datatypes

GCC provides some additional datatypes to the C programming langauge not defined by the standard. These are:

Note that 80- and 128-bit floating point values are not supported on all architectures (they are supported on common x86 and x86_64 systems, though). On ARM platforms, half-precision (16-bit) floating points are supported.

Ranges in switch/case

A GCC extension provides the support for ranges in switch/case statements, so you can have a case for values between 10 and 1000, for instance. A range is defined as x ... y, where x is the lower-bound and y is the upper-bound. You may not leave the spaces before and after the dots out. An example switch statement using cases with ranges:

switch(x){
  case 0 ... 9:
    puts("One digit"); break;
  case 10 ... 99:
    puts("Two digits"); break;
  case 100 ... 999:
    puts("Three digits"); break;
  default:
    puts("I sense a disturbance in the force");
}

This is more convenient than writing 1000 different cases (but you wouldn’t solve the problem like that, would you?).

Binary literals

GCC supports binary literals in C programs using the 0b prefix, pretty much like you would use 0x for hexadecimal literals. In the following example, we initialize an integer using a binary literal for its value:

int integer=0b10111001;