Monday, September 27, 2010

Recursion

Twisting. A new way to think and analyze algorithms. Its structure seems that can be exploitable with multicore systems, excepting of course the size of stacks... In essence, Recursion is a function that calls itself until certain condition is met. And this simple essence is still twisting...

You can define a function as:
function hola() { 
echo "hola!";
}
To make hola() recursive, we need to call hola() inside hola():
function hola() { 
echo "hola!";
hola();
}
But if we execute hola() right now, it will execute forever! We still need some condition that stops that infinite recursion:
function hola($n) {
if($n<=0) return;
echo "hola!";
hola($n-1);
}
And then, a recursive function was born. This is a completely too big jump away from sequential programming! Just try to solve factorial, fibonacci, quicksort and backtracking by using loops only, and compare them with their recursive counterparts... Twisting!

The 'Hello, World!' of recursion, Factorial:
function fact($n){
if($n<=1) return $n;
return $n * fact($n-1);
}
Right after factorial, the next example is Fibonacci:
function fibo($n){
if($n<1) return 0;
if($n==1) return 1;
return fibo($n-1) + fibo($n-2);
}
Fibonacci recursion still twists me, just like any QuickSort algorithm:
function qs($list){
if(count($list)<2) return $list;

$less=array();
$more=array()
$pivot=$list[(int) (count($list)/2)];

foreach($list as $e){
if($e<$pivot) $less[]=$e;
else $more[]=$e;
}
return array_merge( qs($less), qs($more) );
}
And, if that was not enough twist, there's also a Backtracking recursive algorithm! You can look an example of it at CodingBat, using Java. Backtracking is useful for solving problems similar to Knapsack and Eight Queens puzzles.
function backtracking($start, $charArray, $counter = ""){
if($start >= count($charArray)) return;
echo $counter, $charArray[$start], '<br />';
backtracking($start + 1, $charArray, $counter);
backtracking($start + 1, $charArray,
$counter . $charArray[$start]);
}
backtracking(0, array("A","B","C","D"));
I am starting to think that recursion (or at least my knowledge of recursion) is still in diapers.

-------

What follows now is a curiosity I found in Python.

I coded a solution for the previous backtrack recursion in CodingBat by using loops and binary numbers. That solution is good for an amount of elements less than 32 (int) or 64 (long) . Python has "unlimited" integers, so I tested if I can create an integer with a googol of bits and typed:

a = 1<<(10**100)
OverflowError: long int too large to convert to int

Experimenting with previous expression, I assume the limit is:

a = 1 << ((1 << 31) - 1)
print a

OverflowError: long is too large to format

This means 2,147,483,648 (more than two thousand millions) elements, an amount still lower than the amount of people in Earth; Although, in terms of integers, with 64 elements (bits), you can express a number like 9, 223,372, 036,854, 775,808 (more than nine trillions), a number good enough for some kind of accounting.

Python can't format and print (1 << ((1 << 31) - 1)), but at least we can know how many digits it has:

import math
math.log10(1 << ((1 << 31) - 1))

646456992.94488049

The number we can express in Python has 646,456,993 (more than six hundred millions) digits! But we can't print it. That number in ASCII string will weight 617MB. The same number in binary storage should weight 256MB, but it seems Python has something like Computational Notation to store binary strings (analogous to Scientific Notation), because it handles these calculations very well.

Bit: data? instruction? element? state? number? group?

No comments:

Post a Comment