Gninneh.dk

A recursive function or method is one that calls itself. Let us look at an example. A fibonacci number is the sum of it two previous fibonacci numbers. Given the equation below,

we can easily calculate fib(0) which gives 0. fib(1) gives 1, but already by fib(2) the function calls itself twice. Needless to say, the calculations for — say fib(40) — involve a lot of calls to fib: fib(40) calls (fib(39) + fib(38)) – both fib(39) and fib(38) call two lower themselves. fib(40) and fib(39) make the same call to fib(38), so that may be optimized. The sequence is: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181…

C:
The C-code for finding the n‘th fibonacci number, using a recursive function is shown below:

#include 

int main (int argc, const char * argv[]) {
	int a=atoi(argv[1]);
	printf("%d\n",fib(a));
	return 0;
}

int fib (int n){
	if (n >= 2)
		return fib(n - 1) + fib(n - 2);
	else return n; // fib(0)=0 and fib(1)=1
}

The code is correct, and you can put into your text editor (without the line numbers), save the document as a plain text file, let’s say “fib.c” and then open Terminal and type: gcc fib.c -o fib, and then you’ve compiled a program to be run in Terminal. fib.c was the source code, fib is the program name. You run it by typing ./fib 20 which outputs the twentieth fibonacci number. Be aware, at about ./fib 40 it begins taking several seconds. You can always abort it by pressing ctrl+c, if you chose a demanding number.

Java:
The corresponding java-code is:

public class fib {
    public static void main(String[] args) {
         int n=Integer.parseInt(args[0]);
        System.out.println(fib(n));
    }

    private static int fib(int n){
        if (n >= 2)
            return fib(n - 1) + fib(n - 2);
        else return n;
    }
}

Also a ready to employ source code. Lets save the document as fib.java. To compile it, go to your favorite application, Terminal, and compile it: javac fib.java. To run it, type java fib 20. Note, the compiled file is called fib.class, but you only type java fib 20 to execute it. Now you have the same application in C and java – and it is easy to compare speeds. It surprises me, that java is as fast I experience here — let’s test the speeds.

Speed comparison, C and Java
In C:
./fib 30: 0.037s
./fib 40: 3.526s
./fib 41: 5.688s
./fib 42: 9.237s
The test command and its output:
$ time ./fib 43
701408733

real 0m14.922s
user 0m14.906s
sys 0m0.011s

In Java:
java fibj 30: 0.207s
java fibj 40: 2.358s
java fibj 41: 3.658s
java fibj 42: 5.810s
The test command and its output
$ time java fibj 43
701408733

real 0m9.310s
user 0m9.230s
sys 0m0.044s

This is a surprise – Java is not only almost as fast as C – it’s a lot faster! Normally, C is the king of speed, but as mentioned in the top – the code could be optimized, and maybe the Java Virtual Machine takes care of the repetitive calls with the same parameters, which the operating system should take care of in case of C.

Scheme:
Now to an other interesting language, Scheme. All operators and functions act the same way, so + – / * are actually functions, with the function name first and operands following. For example:

> (* 2 3)
6

There are no loops, so functions have to be recursive if you need repetitive behavior. The fib program in scheme looks like:

(define fib
    (lambda (n)
        (if(= n 0)
                   0
        (if(= n 1)
                   1
                (if(> n 1)
                   (+ (fib (- n 1)) (fib (- n 2))))))))

That’s defining the function – to run it, you just start using it right after – it compiles itself when necessary.

> (fib 30)
832040
> (fib 33)
3524578
> (fib 35)
9227465

(fib 35) took 17 seconds. A little more for long calculations, but the time it takes to write a scheme function makes up for the slower run-time. Scheme has other advantages like calculating with arbitrarily long numbers. A function which calculates 845! takes two minutes to write, and the output several 100 digits:

It is another recursive function:

(define factorial
  (lambda (n)
    (if (<= n 0)
        1
        (* n (factorial (- n 1))))))

(factorial 1000) takes less time than I could measure it (<.5 s).

Finally, I decided to move on to using WordPress for my site.

The former site was dificult to maintain as I had to hardcode any changes of content including image galleries into the html, php, and javascript code.

Now, I will be updating the site more frequently.