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.