Friday, January 05, 2007

Basic Recursion

I found out that many programmers that are not academic educated but self learners don't know recursion. And this is something that might safe your life pretty fast sometimes ... so I will drop a few lines about it and why use it.


Recursion, in mathematics and computer science, is a method of defining functions in which the function being defined is applied within its own definition. The term is also used more generally to describe a process of repeating objects in a self-similar way. For instance, when the surfaces of two mirrors are almost parallel with each other the nested images that occur are a form of recursion.
/description from Wikipedia/

I actually find pretty confusing the example with the mirrors for someone who is hearing for the first time about recursion. So I will give one from me:
"Drawing a tree structure from the folders and sub folders of your computer hard drive is made with recursion."

So as I expect my audience to be people from the IT sector or at least people generally known to software or programming at least at a basic level I will give an example of this with web based category navigation.

So we have something like 1 is the root of 2 and 3.
And 2 is the root of 4.
It looks like this:
1
|-2
_|-4
|-3


php code example:




// Making the function to draw the tree ***RECURSION IN MIND***
function tree($id='0',$spacer="          "){
$query = "SELECT * FROM categories WHERE parent_id='$id'";
$result = mysql_query($query);
while ($row = mysql_fetch_array($result)) {
echo $spacer.'img src="images/folder.png" border="0" /> '.
$row['title'].'   '.
'a href="index.php?module=ADMIN">'.'add'.'/a> | '.
'a href="index.php?module=ADMIN" style="font-size:9px;">'.'edit'.'/a>
';
// The RECURSION
tree($row['id'],$spacer."          ");
}
}

// Calling the function
tree();





This is old code that I posted accidentally without looking at it that it is not recursion sorry about this... I will leave it in case someone find it useful ;)



public function navigation($id) {
$navigation = '';

$this->initdb();
$sql = "SELECT `id`,`name`,`description`,`parent_id`
FROM `category`
WHERE `id` = '$id'
LIMIT 1";

$res = $this->db->query($sql);
$row = $res->fetchRow(MDB2_FETCHMODE_ASSOC);
$navigation .= $row['name'];
$parent_id = $row['parent_id'];

while($parent_id != 0) {
$sql = "SELECT `id`,`name`,`description`,`parent_id`
FROM `category`
WHERE `id` = '$parent_id'
LIMIT 1";

$result = $this->db->query($sql);
$row = $result->fetchRow(MDB2_FETCHMODE_ASSOC);

// REVERSE THE BUILD
$navigation = $row['name'].' > '.$navigation;

$parent_id = $row['parent_id'];
}

//$this->checkPearError($result);
return $navigation;
}






I hope that the example is clear to understand... for those with PHP and MySQL knowledge it shouldn't be a problem even if they never used the MDB2 pear package.
Recursion is very useful in those situations where you need repetitive work.

This is working code from a project I participate in and this chunk is written by me :-p
So yes it actually works ;-)

So I hope I gave light on this topic!
Good night folks.

3 comments:

Anonymous said...

I'm sorry mate, that's not Recursion. Recursion is when a function calls itself.

It's more like this... (pseudo code of course)

function nav(id)
{
//code to get parent of id
parent = ...; //parent name
parentid = ...; //parent id
if(parentid == 0)
{
return;
}
return nav(parentid).'>'.parent;
}

Явор Иванов said...

Sorry about this wrong stuff! I didn't looked at the code really I just take the piece of code and drop it there cause my memory was about recursion in it... sorry I now posted a real RECURSION example... thanks mate!

I appreciate this!

Anonymous said...

precisly, the function in the post doesnt have anything to do with recursion. Definition of a recursion is a function that calls itself, just like the function posted in the previous comment.

Furthermore, recursion are of more powerful usage in function oriented programming languages.