[SOLVED] recursive loop causing apache to crash!

skibum · September 20, 2008

Hi,

I am trying to use a recursive loop to find a combination of items (Foos) that are linked somehow. The Foos are just integers and my Bar class is supposed to take an array of Foos and return either an array of Foos in the order they are linked or false if no possible linked combination exists.

The problem is that my code seems to crash apache. I know it is the code because every other bit of code I have works fine which leads me to think I am causing the stack to overflow with a leak somewhere.

Anyway, can someone please have a look and show me where I am going wrong.

<?php

$foos = array(31, 23, 37, 15, 45);
$bar = new Bar();
$bestFoos = $bar->findBestFoos($foos);
print_r($bestFoos);
echo ' end ';

class Bar {
//	a bar is an object that manipulates all things foo

public function findBestFoos($foos)
{
	foreach($foos as $f)
	{
		$combo = array();
		$combo[] = $f;
		$results = $this->recursiveCombos($combo);
		if($results)
		{
			return $results;
		}
	}
	return FALSE;	
}

private function recursiveCombos($combo)
{
	//	recurively checks to see if a linked combo exists and returns it or false
	if(count($combo) != count($this->links) && $combo)
	{	
		//	not complete
		$current = end($combo);
		$thislink = $this->links[$current];
		foreach($thislink as $l)
		{
			//	add the next match if present
			if(array_key_exists($l, $this->links[$current]))
			{
				$combo[] = $l;
				print_r($combo);
			}
			else
			{
				//	go back one step
				$pos = array_pop($combo);
				if(!$pos)
				{
					return FALSE;
				}
			}
			$this->recursiveCombos($combo);
		}
	}
	else
	{
		//	success
		return $combo;
	}
}

//	big fat array to simulate database calls and map links between foos (8x8 square)
public $links = array(
				1 => array(2, 9, 10),		
				2 => array(1, 3, 9, 10, 11),		
				3 => array(2, 4, 10, 11, 12),		
				4 => array(3, 5, 11, 12, 13),		
				5 => array(4, 6, 12, 13, 14),		
				6 => array(5, 7, 13, 14, 15),		
				7 => array(6, 8, 14, 15, 16),		
				8 => array(7, 15, 16),		
				9 => array(1, 2, 10, 17, 18),		
				10 => array(1, 2, 3, 9, 11, 17, 18, 19),		
				11 => array(2, 3, 4, 10, 12, 18, 19, 20),		
				12 => array(3, 4, 5, 11, 13, 19, 20, 21),		
				13 => array(4, 5, 6, 12, 14, 20, 21, 22),		
				14 => array(5, 6, 7, 13, 15, 22, 22, 23),		
				15 => array(6, 7, 8, 14, 16, 22, 23, 24),		
				16 => array(7, 8, 15, 23, 24),		
				17 => array(9, 10, 18, 25, 26),		
				18 => array(9, 10, 11, 17, 19, 25, 26, 27),		
				19 => array(10, 11, 12, 18, 20, 26, 27, 28),		
				20 => array(11, 12, 13, 19, 21, 27, 28, 29),
				21 => array(12, 13, 14, 20, 22, 28, 29, 30),		
				22 => array(13, 14, 15, 21, 23, 29, 30, 31),		
				23 => array(14, 15, 16, 22, 24, 30, 31, 32),		
				24 => array(15, 16, 23, 31, 32),		
				25 => array(17, 18, 26, 33, 34),
				26 => array(17, 18, 19, 25, 27, 33, 34, 35),		
				27 => array(18, 19, 20, 26, 28, 34, 35, 36),		
				28 => array(19, 20, 21, 27, 29, 35, 36, 37),		
				29 => array(20, 21, 22, 28, 30, 36, 37, 38),		
				30 => array(21, 22, 23, 29, 31, 37, 38, 39),		
				31 => array(22, 23, 24, 30, 32, 38, 39, 40),		
				32 => array(23, 24, 31, 39, 40),		
				33 => array(24, 26, 34, 41, 42),		
				34 => array(25, 26, 27, 33, 35, 41, 42, 43),		
				35 => array(26, 27, 28, 34, 36, 42, 43, 44),		
				36 => array(27, 28, 29, 35, 37, 43, 44, 45),		
				37 => array(28, 29, 30, 36, 38, 44, 45, 46),		
				38 => array(29, 30, 31, 37, 39, 45, 46, 47),		
				39 => array(30, 31, 32, 38, 40, 46, 47, 48),		
				40 => array(31, 32, 39, 47, 48),		
				41 => array(33, 34, 42, 49, 50),		
				42 => array(33, 34, 35, 41, 43, 49, 50, 51),		
				43 => array(34, 35, 36, 42, 44, 50, 51, 52),		
				44 => array(35, 36, 37, 43, 45, 51, 52, 53),		
				45 => array(36, 37, 38, 44, 46, 52, 53, 54),		
				46 => array(37, 38, 39, 45, 47, 53, 54, 55),		
				47 => array(38, 39, 40, 46, 48, 54, 55, 56),		
				48 => array(39, 40, 47, 55, 56),		
				49 => array(41, 42, 50, 57, 58),		
				50 => array(41, 42, 43, 49, 51, 57, 58, 59),		
				51 => array(42, 43, 44, 50, 52, 58, 59, 60),		
				52 => array(43, 44, 45, 51, 53, 59, 60, 61),		
				53 => array(44, 45, 46, 52, 54, 60, 61, 62),		
				54 => array(45, 46, 47, 53, 55, 61, 62, 63),		
				55 => array(46, 47, 48, 54, 56, 62, 63, 64),		
				56 => array(47, 48, 55, 63, 64),		
				57 => array(49, 50, 58),		
				58 => array(49, 50, 51, 57, 59),		
				59 => array(50, 51, 52, 58, 60),		
				60 => array(51, 52, 53, 59, 61),		
				61 => array(52, 53, 54, 60, 62),		
				62 => array(53, 54, 55, 61, 63),		
				63 => array(54, 55, 56, 62, 64),		
				64 => array(55, 56, 63)
				);
}
?>

skibum · September 20, 2008

Found the problem.

The code below now works

<?php

$foos = array(31, 23, 38, 15, 45);
$bar = new Bar();
$bestFoos = $bar->findBestFoos($foos);
print_r($bestFoos);
if($bestFoos) {
echo ' sucess ';
}
echo ' end ';

class Bar {
//	a bar is an object that manipulates all things foo

public function findBestFoos($foos)
{
	foreach($foos as $f)
	{
		$combo = array();
		$combo[] = $f;
		$results = $this->recursiveCombos($combo, $foos);
		if($results)
		{
			return $results;
		}
	}
	return FALSE;	
}

private function recursiveCombos($combo, $foos)
{
	//	recurively checks to see if a linked combo exists and returns it or false
	if(count($combo) == count($foos))
	{	
		//	success
		return $combo;
	}
	else
	{
		if(count($combo) == 0)
		{
			return FALSE;
		}
		else
		{
			//	not complete
			$current = end($combo);
			$thislink = $this->links[$current];
			//print_r($thislink);
			foreach($thislink as $l)
			{
				//	add the next match if present
				if(in_array($l, $foos) && !in_array($l, $combo))
				{
					$combo[] = $l;
					if(count($combo) == count($foos))
					{
						return $combo;
					}
					$results = $this->recursiveCombos($combo, $foos);
					return $results;
				}
			}
			//	go back one step
			$pos = array_pop($combo);
			if(!$pos)
			{
				echo 'arrrra';
				return FALSE;
			}
		}
	}
}

//	big fat array to simulate database calls and map links between foos (8x8 square)
public $links = array(
				1 => array(2, 9, 10),		
				2 => array(1, 3, 9, 10, 11),		
				3 => array(2, 4, 10, 11, 12),		
				4 => array(3, 5, 11, 12, 13),		
				5 => array(4, 6, 12, 13, 14),		
				6 => array(5, 7, 13, 14, 15),		
				7 => array(6, 8, 14, 15, 16),		
				8 => array(7, 15, 16),		
				9 => array(1, 2, 10, 17, 18),		
				10 => array(1, 2, 3, 9, 11, 17, 18, 19),		
				11 => array(2, 3, 4, 10, 12, 18, 19, 20),		
				12 => array(3, 4, 5, 11, 13, 19, 20, 21),		
				13 => array(4, 5, 6, 12, 14, 20, 21, 22),		
				14 => array(5, 6, 7, 13, 15, 22, 22, 23),		
				15 => array(6, 7, 8, 14, 16, 22, 23, 24),		
				16 => array(7, 8, 15, 23, 24),		
				17 => array(9, 10, 18, 25, 26),		
				18 => array(9, 10, 11, 17, 19, 25, 26, 27),		
				19 => array(10, 11, 12, 18, 20, 26, 27, 28),		
				20 => array(11, 12, 13, 19, 21, 27, 28, 29),
				21 => array(12, 13, 14, 20, 22, 28, 29, 30),		
				22 => array(13, 14, 15, 21, 23, 29, 30, 31),		
				23 => array(14, 15, 16, 22, 24, 30, 31, 32),		
				24 => array(15, 16, 23, 31, 32),		
				25 => array(17, 18, 26, 33, 34),
				26 => array(17, 18, 19, 25, 27, 33, 34, 35),		
				27 => array(18, 19, 20, 26, 28, 34, 35, 36),		
				28 => array(19, 20, 21, 27, 29, 35, 36, 37),		
				29 => array(20, 21, 22, 28, 30, 36, 37, 38),		
				30 => array(21, 22, 23, 29, 31, 37, 38, 39),		
				31 => array(22, 23, 24, 30, 32, 38, 39, 40),		
				32 => array(23, 24, 31, 39, 40),		
				33 => array(24, 26, 34, 41, 42),		
				34 => array(25, 26, 27, 33, 35, 41, 42, 43),		
				35 => array(26, 27, 28, 34, 36, 42, 43, 44),		
				36 => array(27, 28, 29, 35, 37, 43, 44, 45),		
				37 => array(28, 29, 30, 36, 38, 44, 45, 46),		
				38 => array(29, 30, 31, 37, 39, 45, 46, 47),		
				39 => array(30, 31, 32, 38, 40, 46, 47, 48),		
				40 => array(31, 32, 39, 47, 48),		
				41 => array(33, 34, 42, 49, 50),		
				42 => array(33, 34, 35, 41, 43, 49, 50, 51),		
				43 => array(34, 35, 36, 42, 44, 50, 51, 52),		
				44 => array(35, 36, 37, 43, 45, 51, 52, 53),		
				45 => array(36, 37, 38, 44, 46, 52, 53, 54),		
				46 => array(37, 38, 39, 45, 47, 53, 54, 55),		
				47 => array(38, 39, 40, 46, 48, 54, 55, 56),		
				48 => array(39, 40, 47, 55, 56),		
				49 => array(41, 42, 50, 57, 58),		
				50 => array(41, 42, 43, 49, 51, 57, 58, 59),		
				51 => array(42, 43, 44, 50, 52, 58, 59, 60),		
				52 => array(43, 44, 45, 51, 53, 59, 60, 61),		
				53 => array(44, 45, 46, 52, 54, 60, 61, 62),		
				54 => array(45, 46, 47, 53, 55, 61, 62, 63),		
				55 => array(46, 47, 48, 54, 56, 62, 63, 64),		
				56 => array(47, 48, 55, 63, 64),		
				57 => array(49, 50, 58),		
				58 => array(49, 50, 51, 57, 59),		
				59 => array(50, 51, 52, 58, 60),		
				60 => array(51, 52, 53, 59, 61),		
				61 => array(52, 53, 54, 60, 62),		
				62 => array(53, 54, 55, 61, 63),		
				63 => array(54, 55, 56, 62, 64),		
				64 => array(55, 56, 63)
				);
}
?>

Sign In

[SOLVED] recursive loop causing apache to crash!

Recommended Posts

skibum

Link to comment

Share on other sites

skibum

Link to comment

Share on other sites

Archived

Browse

Activity

Important Information