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.

4 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;
}

Yavor Ivanov 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.

dfadf said...

Microsoft Office
Office 2010
Microsoft Office 2010
Office 2010 key
Office 2010 download
Office 2010 Professional
Microsoft outlook
Outlook 2010
Windows 7
Microsoft outlook 2010