Recursive functions explained

>>>Recursive functions explained

Recursive functions explained

In programming there are sometimes situations when you have to recursively call a function from itself. Novice programmers might find it difficult to understand so here are my two examples written in PHP.

Recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem. A typical example is factorial which of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. Then 3! equals to 3×2×1=6; 5! = 5×4×3×2×1 = 120, etc.

Factorial

To program a factorial function we need to note that calculating n factorial will involve multiplying n by n-1 factorial and so on. By using recursive function we do not need to perform cycles: the same function calls itself with diffrent arguments. In PHP it would look like this:

function factorial($n) {
	if($n<=1) {
		return 1;
	}
	else {
		return $n*factorial($n-1);
	}
}

When we execute factorial(3) the function gets 3 as an argument, checks if it is not equal or less than 1 (as it has to be non-negative and considering 0! = 1) and multiplies it by factorial of 2 – the same function called with argument 2. When n reaches 1, recursion is finished. Each recursive function must have a terminating condition otherwise it will stuck in a infinite loop.

Children of tree nodes

Another, more sophisticated example is retrieving hierarchical structure from RDBMS. In my MSc thesis I compare recursive rendering of trees with another approach, so had to code them both to make experiment.

The tree is stored in database table with each node having identifier and parent ID. Rendering the tree in recursive approach means we have to retrieve children of root node, then of any other node and so on. Here is recursive function performing this task:

function recursion_children($parent_id, $recursive=true) {
	$result = mysql_query("SELECT nodeid, parent, title FROM hierarchy WHERE parent=".$parent_id." ORDER BY nodeid ASC;");
	while($row = mysql_fetch_array($result)) {
		echo("<li>".$row["title"]);
		if($recursive==true) {
			echo("\n <ul>");
			recursion_children($row['nodeid']);
			echo("\n </ul>\n");
		}
		echo("</li>\n");
	}
}

Notice function argument $recursive which is true by default. I’ve added it for this function to be either recursive or not: if argument is true, then function renders children of all nodes; if false, only children of root node will be printed.

These two examples illustrate that programming recursive functions to perform certain tasks is pretty straightforward.

2016-10-24T10:56:53+00:00 2011-05-27|Programming|3 Comments

About the Author:

Gytis Repečka is System analyst with passion to open source, electronics & cars, spreading bits about tech, music and privacy.

3 Comments

  1. Igor 2011-05-27 at 15:09 - Reply

    To understand recursion, you must first understand recursion.

    • Gytis Repečka 2011-05-27 at 15:37 - Reply

      Like in recursive acronyms, where PHP stands for “PHP Hypertext Preprocessor” 😀

      • Hamhong 2012-03-12 at 16:00 - Reply

        In your first example (the vtreatiie one), the code would run a little faster through each trip in the loop if you simplified the comparison. Instead of <=, try using !=. The former requires more machine instructions to calculate than the latter.For !=, we see if it's equal and if not, we make another trip through the loop. Since your for loop is set up with i=0, then you don't have to worry about whether i is greater-than or less-than input, you can just care if it's equal.

Leave A Comment