[RESOLVED] Mind boggling recursion script! Help!!

Paul_help_ · Oct 2, 2016

Hi Guys. I am currently in the process of reading though a php book and there is a recursion script I have been examining and trying to understand.

Basically, what this script does is allow the user to type a name of a folder/directory to search for and then output the results, giving the full path of where the file is located (if it exists) and a message telling the user the directory doesn't exist, if it doesn't exist.

So what I did was create some dummy folders and create other dummy folders inside them folders.

I used these folders to test the script.

I ran the script, searching for a folder named "images", and the following was output in the browser:

Searching for 'images' in '.' ...
The following folders matched your search:

./home/matt/images
./home/paul/images
./home/paul/yeah/haha/images
./images[/QUOTE]

Here is the script:

<html>
<head>
<title>Practice PHP</title>
<link rel="stylesheet" type="text/css" href="common.css">
<style type="text/css">
table, td, th {
border: 1px solid;

}

.altrow {

background-color: ff0000;

}


</style>

</head>
<body>



<?php
define( "TOP_LEVEL_DIR", "." );
if ( isset( $_POST['posted'] ) ) {
// Get the folder to search for
$folderName = isset( $_POST['folderName'] ) ? $_POST['folderName'] : "";
// Search for the folder


echo "<p>Searching for '$folderName' in '" . TOP_LEVEL_DIR . "' ...</p>";
$matches = array();
searchFolder( TOP_LEVEL_DIR, $folderName, $matches );
// Display any matches
if ( $matches ) {
echo "<h2>The following folders matched your search:</h2>\n<ul>\n";
foreach ( $matches as $match ) echo ( "<li>$match</li>" );
echo "</ul>\n";
} else {
echo "<p>No matches found.</p>";
}
}
/**
* Recursively searches a directory for a subdirectory
*
* @param string The path to the directory to search
* @param string The subdirectory name to search for
* @param stringref The current list of matches
*/
function searchFolder( $current_folder, $folder_to_find, &$matches )
{
if ( !( $handle = opendir( $current_folder ) ) ) die( "Cannot open $current_
folder." );
while ( $entry = readdir( $handle ) ) {
if ( is_dir( "$current_folder/$entry" ) ) {
if ( $entry != "." && $entry != ".." ) {
// This entry is a valid folder
// If it matches our folder name, add it to the list of matches
if ( $entry == $folder_to_find ) $matches[] = "$current_folder/$entry";
// Search this folder
searchFolder( "$current_folder/$entry", $folder_to_find, $matches );
}
}
}
closedir( $handle );
}
// Display the search form
?>
<form method="post" action="">
<div>
<input type="hidden" name="posted" value="true" />
<label>Please enter the folder to search for:</label>
<input type="text" name="folderName" />
<input type="submit" name="search" value="Search" />
</div>
</form>
</body>
</html>

......... now getting to my confusion.

What I am struggling to understand is how the code, above, is able to output a path string as long as this:

./home/paul/yeah/haha/images

.... I don't understand how the fist 3 folders:

./home/paul/yeah/

.... are even stored in memory as a string.

I find this really mind boggling and confusing.

I mean, this code:

$entry = readdir( $handle )

....... should only be able to read one directory at a time right??

so how does:

"current_folder/$entry"

..... manage to store a string as long as:

./home/paul/yeah/haha/images

..... when it is stored in the $matches array?

Please help me!

Paul.

NogDog · Oct 3, 2016

When the function calls itself, it appends the current directory with the next one it wants to search:

                searchFolder( "[COLOR="#FF0000"][B]$current_folder/$entry[/B][/COLOR]", $folder_to_find, $matches );

NogDog · Oct 3, 2016

PS: And since $matches is passed by reference, it's the same array being added to in any level of the recursion.

Weedpacket · Oct 3, 2016

As soon as the complexity gets above a single if() branch, it helps to format the code (and use [noparse]

[/noparse] tags instead of [noparse][code=html][/noparse]).
[code=php]<html>
<head>
<title>Practice PHP</title>
<link rel="stylesheet" type="text/css" href="common.css">
<style type="text/css">
table, td, th {
border: 1px solid;
}
.altrow {
background-color: ff0000;
}
</style>

</head>
<body>
<?php
define( "TOP_LEVEL_DIR", "." );
if ( isset( $_POST['posted'] ) ) {
	// Get the folder to search for
	$folderName = isset( $_POST['folderName'] ) ? $_POST['folderName'] : "";
	// Search for the folder

echo "<p>Searching for '$folderName' in '" . TOP_LEVEL_DIR . "' ...</p>";
$matches = array();
searchFolder( TOP_LEVEL_DIR, $folderName, $matches );
// Display any matches
if ( $matches ) {
	echo "<h2>The following folders matched your search:</h2>\n<ul>\n";
	foreach ( $matches as $match ) echo ( "<li>$match</li>" );
	echo "</ul>\n";
} else {
	echo "<p>No matches found.</p>";
}
}

/**
* Recursively searches a directory for a subdirectory
*
* @param string The path to the directory to search
* @param string The subdirectory name to search for
* @param stringref The current list of matches
*/
function searchFolder( $current_folder, $folder_to_find, &$matches )
{
	if ( !( $handle = opendir( $current_folder ) ) ) die( "Cannot open $current_folder." );
	while ( $entry = readdir( $handle ) ) {
		if ( is_dir( "$current_folder/$entry" ) ) {
			if ( $entry != "." && $entry != ".." ) {
				// This entry is a valid folder
				// If it matches our folder name, add it to the list of matches
				if ( $entry == $folder_to_find ) $matches[] = "$current_folder/$entry";
				// Search this folder
				searchFolder( "$current_folder/$entry", $folder_to_find, $matches );
			}
		}
	}
	closedir( $handle );
}
// Display the search form
?>
<form method="post" action="">
<div>
<input type="hidden" name="posted" value="true" />
<label>Please enter the folder to search for:</label>
<input type="text" name="folderName" />
<input type="submit" name="search" value="Search" />
</div>
</form>
</body>
</html>

(And I can see that there's at least one place where things are being done in what I would say is backwards... and the doc comment is wrong - it's an array reference, not a string reference)

To answer your last question, items are stored in the [font=monospace]$matches[/font] array in this line:

				// If it matches our folder name, add it to the list of matches
				if ( $entry == $folder_to_find ) $matches[] = "$current_folder/$entry";

And if by "long" you mean "has more than one directory component": [font=monospace]$current_folder[/font] has the whole path From [font=monospace]TOP_LEVEL_DIR[/font] down to the current directory, and then [font=monospace]searchFolder[/font] gets called with the current path combined with each subdirectory directory in turn, in

searchFolder( "$current_folder/$entry", $folder_to_find, $matches );

So if you looked at [font=monospace]$current_folder[/font] at the various times you go into that search function, you'll see it getting longer and longer as you go deeper into the tree. And when appropriate, that's what is being appended to the [font=monospace]$matches[/font] array.

pbismad · Oct 3, 2016

To understand this, just look at the main code's call to the function and the function definition -

// function call in the main code
searchFolder( TOP_LEVEL_DIR, $folderName, $matches );

// function definition
function searchFolder( $current_folder, $folder_to_find, &$matches )
{
	if ( !( $handle = opendir( $current_folder ) ) ) die( "Cannot open $current_folder." );
	while ( $entry = readdir( $handle ) ) {
		if ( is_dir( "$current_folder/$entry" ) ) {
			if ( $entry != "." && $entry != ".." ) {
				// This entry is a valid folder
				// If it matches our folder name, add it to the list of matches
				if ( $entry == $folder_to_find ) $matches[] = "$current_folder/$entry";
				// Search this folder
				searchFolder( "$current_folder/$entry", $folder_to_find, $matches );
			}
		}
	}
	closedir( $handle );
}

The key to understanding how a recursive function works is to understand that each call to the function creates a new local set of variables. The three variables that have been defined for the parameters -$current_folder, $folder_to_find, $matches, and the $handle and $entry variables are all new and separate for each call to the function. Technically, this is accomplished through storing the data on a LIFO (last in first out) stack.

When the main code calls the function, it supplies three call time VALUES as parameters. The first value happens to come from a defined constant and the other two happen to come from main program variables. These VALUES are assigned to the current local $current_folder, $folder_to_find, and $matches (this is actually assigned a reference to the supplied value due to the &) variables.

The code in the function runs to open the folder given by the value in the current local $current_folder variable, to match any current entry given by the value in the current local $folder_to_find variable, and stores any matching path, as an array entry, in the current local $matches variable, which is a reference to the value that was initially supplied when the function was called, which is a main program array variable.

When the code inside the function finds a entry that is a folder, it calls the searchFolder() function recursively and passes the following three call time VALUES - "$current_folder/$entry", $folder_to_find, and $matches. The second and third parameters are just being passed through, as is. What's important is the first parameter. It's made up of the current local $current_folder and the $entry that was found, and it becomes the $current_folder input to the next invocation of the searchFolder() function.

This repeats for each entry that's found that is a folder.

When any level of the the searchFolder() function is done looping over the directory it was given as its current local $current_folder value, it returns to the calling code. This pops the local variables off of the stack. This leaves the stack in the state it was in when the function was called. If the calling code happens to be a lower level of the searchFolder() function, as far as that instance of the function knows, it's still trying to loop over the directory it was given as its current local $current_folder value.

This repeats back until the instance of the function that was called by the main code finishes looping over the initial starting directory it was given as its current local $current_folder value.

Paul_help_ · Oct 3, 2016

thanks guys, after examining the code again, it makes sense now.

[RESOLVED] Mind boggling recursion script! Help!!

PPaul_help_

NogDog

NogDog

Weedpacket

Ppbismad

PPaul_help_