UltraMega Blog
9Feb/104

PHP: Recursive Functions

A recursive function is a function that calls itself. This is useful for certain applications. This short tutorial will show an example of a recursive function in action.

Let's say we have the following array of categories. Normally this might be stored in a database, but we'll use an array here for simplicity.

/* Example category hierarchy:
    Tutorials
    - PHP
    -- OOP
    -- Tips
    - JavaScript
    -- Basics
    -- Frameworks
    --- jQuery
    --- MooTools
    News
    - PHP
    - Wordpress
*/
$cats = array();
$cats[1] = array('parent' => 0, 'title' => 'Tutorials');
  $cats[2] = array('parent' => 1, 'title' => 'PHP');
    $cats[3] = array('parent' => 2, 'title' => 'OOP');
    $cats[4] = array('parent' => 2, 'title' => 'Tips');
  $cats[5] = array('parent' => 1, 'title' => 'JavaScript');
    $cats[6] = array('parent' => 5, 'title' => 'Basics');
    $cats[7] = array('parent' => 5, 'title' => 'Frameworks');
      $cats[8] = array('parent' => 7, 'title' => 'jQuery');
      $cats[9] = array('parent' => 7, 'title' => 'MooTools');
$cats[10] = array('parent' => 0, 'title' => 'News');
  $cats[11] = array('parent' => 10, 'title' => 'PHP');
  $cats[12] = array('parent' => 10, 'title' => 'Wordpress');

In this case, a good application of a recursive function would be to display a breadcrumbs display of a particular category. In the example, we use the key 'parent' to identify the category that a subcategory belongs to, or 0 for the main categories.

Our recursive function would check if parent is greater than 0. If so, the function would return the current category prepended by the result of calling itself with the parent id. If parent is 0, it will just return the name of the category. This way, it will keep adding categories to the chain until it gets to the top. Here's what it looks like:

function breadcrumbs($id) {
    global $cats;
    if($cats[$id]['parent'] > 0) {
        return breadcrumbs($cats[$id]['parent']) . ' -> ' . $cats[$id]['title'];
    }
    return $cats[$id]['title'];
}

What makes this recursive is the fact that the function breadcrumbs() calls breadcrumbs() inside it. It's actually a very simple concept. You just have to be careful and make sure there is an end to the recursion.

Here is a full example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
<?php
/* Example category hierarchy:
    Tutorials
    - PHP
    -- OOP
    -- Tips
    - JavaScript
    -- Basics
    -- Frameworks
    --- jQuery
    --- MooTools
    News
    - PHP
    - Wordpress
*/
$cats = array();
$cats[1] = array('parent' => 0, 'title' => 'Tutorials');
  $cats[2] = array('parent' => 1, 'title' => 'PHP');
    $cats[3] = array('parent' => 2, 'title' => 'OOP');
    $cats[4] = array('parent' => 2, 'title' => 'Tips');
  $cats[5] = array('parent' => 1, 'title' => 'JavaScript');
    $cats[6] = array('parent' => 5, 'title' => 'Basics');
    $cats[7] = array('parent' => 5, 'title' => 'Frameworks');
      $cats[8] = array('parent' => 7, 'title' => 'jQuery');
      $cats[9] = array('parent' => 7, 'title' => 'MooTools');
$cats[10] = array('parent' => 0, 'title' => 'News');
  $cats[11] = array('parent' => 10, 'title' => 'PHP');
  $cats[12] = array('parent' => 10, 'title' => 'Wordpress');
 
function breadcrumbs($id) {
    global $cats;
    if($cats[$id]['parent'] > 0) {
        return breadcrumbs($cats[$id]['parent']) . ' -> ' . $cats[$id]['title'];
    }
    else {
        return $cats[$id]['title'];
    }
}
 
// Examples
echo breadcrumbs(1); // Tutorials
echo breadcrumbs(8); // Tutorials -> JavaScript -> Frameworks -> jQuery
echo breadcrumbs(11); // News -> PHP
?>

Posted by Steve

Comments (4) Trackbacks (0)
  1. aww recursion, something so useful and powerful, but also so frustrating to track back through! What inspired this article?

  2. Thank you, thank you, thank you! I’ve just started learning php and this helped me a lot. I just changed few lines in your function, instead of using global $cats, I added one more argument to breadcrumb function – $catArray, since I get this array once in page and use it a lot for other stuff. Is it better to use method I used (with breadcumbs($id,$catArray) ) or the one You use (with global)?


Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.

No trackbacks yet.