Рекурсивная функция

[4ak]

function factorial($n){
	if ($n == 0) return 1;
		return $n * factorial($n-1); /*считаем factorial(3), php возвращает 3 * factorial(2) далее идет на верх к 
                                               функции factorial($n) и считает уже factorial(2),теперь уже  возвращает 3 * 2 * factorial(1) и тд. 
                                               Но непонятно, что будет при factorial(0). Он же поидее просто вернет 1 при $n=0 и 
                                               что тогда произойдет со всеми остальными вычислениями?*/
}
$result = factorial(5);
	echo "5! = " . $result;

function myCount($item) {
	if(is_null($item))
		return 0;
	if(!is_array($item))
		return 1;
	$cnt=0;              
	foreach($item as $v){




	if($mode==1 and is_array($v))    
	$cnt += myCount($v, 1);
	$cnt++; /* здесь все понятно пока функция считает значения простого массива, 
                                но когда появилась рекурсия для того, чтобы функция считала значения
                                и многоуровнего массива(эти 3 строки) я перестал понимать что делает php. Можете написать, что он делает начиная с цикла foreaach?*/






	}
		return $cnt;
	}

Возникло непонимание с рекурсивной функцией. Первый код - функция факториала, второй код воссоздание функции count. Свои мысли и вопросы написал в комментариях к коду. Могу заблуждаться в порядке действий php, так что если что поправляйте. Заранее спасибо!

[K313]

function factorial3($n){
        if ($n == 0) return 1;
                return $n * factorial2($n-1);
}
function factorial2($n){
        if ($n == 0) return 1;
                return $n * factorial1($n-1);
}
function factorial1($n){
        if ($n == 0) return 1;
                return $n * factorial0($n-1);
}
function factorial0($n){
        if ($n == 0) return 1;
                /*return $n * factorial($n-1);*/
/* здесь мы представим что пришедшая $n уже равна 0, поэтому до нижнего return дело не дойдёт
}

Поменяйте немного ход мыслей и представте что в нижних ретурнах пхп не поднимается на верх к началу функции, а вызывает другую функцию, которая просто делает тоже что и эта...

Вызываем factorial3(3); и проходим по функциям карандашиком

[Int]

Я сокращу название функции, чтобы меньше писать

fc(3) = 3*fc(2) = 3*2*fc(1) = 3*2*1*fc(0) = 3*2*1*1;

На самом деле, лучше писать как-то так:

if ($n < 0) return -1;
if ($n < 2) return 1;
return $n * factorial($n-1);

Это позволит не вычислять факториал нуля каждый раз, и заодно предотвратит вычисление факториала отрицательного числа

Вторая функция считает не значения массива, а что-то типа его мерности.

[Gaspode]

———-

Edited March 1, 2012 by Gaspode

[4ak]

K313, Int

Спасибо, с первой все понятно.

Вторая - аналог существующей функции count, ее я начиная с цикла foreach не понимаю.

[Int]

Странный какой-то count, он точно работает?

Undefined variable: mode

<?
function myCount($item) {
	if(is_null($item))
		return 0;
	if(!is_array($item))
		return 1;
	$cnt=0;              
	foreach($item as $v)
	{
		if(is_array($v))    
		$cnt += myCount($v, 1);
		$cnt++;
}
return $cnt;
}

$a=array(1,2,3,array(10));
echo myCount($a);
?>

Выдаёт 5. Значит не работает как надо.

<?
function myCount($array) {
	$ret=0;
	foreach ($array as $item)
	{
		if (!is_array($item)) $ret++;
		else $ret+=myCount($item);
	}
	return $ret;
}

$a=array(1,2,3,array(10,12,array('a',1)));
echo myCount($a);
?>

Вот мой вариант фунцкции

[4ak]

  On 3/1/2012 at 7:12 AM, Int said:

Странный какой-то count, он точно работает?

Выдаёт 5. Значит не работает как надо.

В этом массиве $a = array(1,2,3,array(10)) как раз 5 элементов, можно проверить стандартной функцией count(a,1)(1 - используется для многомерных массивов, по умолчанию стоит 0.) Это как раз аргумент mode который я забыл вписать в функцию, хотя там было условие с mode в if, но php выдавал

  On 3/1/2012 at 7:12 AM, Int said:

Undefined variable: mode

и ты удалил условие.

Вот работающий код:.

function myCount($item, $mode=0) {
	if(is_null($item))/**/
		return 0;
	if(!is_array($item))
		return 1;
	$cnt=0;
	foreach($item as $v){
	if($mode==1 and is_array($v))
	$cnt += myCount($v, 1);
	$cnt++;
	}
		return $cnt;
	}

$a=array(1,2,3,array(10));
echo myCount($a,1);

echo count($a,1);

  On 3/1/2012 at 7:12 AM, Int said:

Вот мой вариант фунцкции

При подсчете этого массива

$a=array(1,2,3,array(10,12,array('a',1)));

твоя функция выдает 7, а оригинальный count($a,1)и myCount($a,1) выдают 9.

В твоей функции я передвинул $ret вниз и все стало правильно считаться, хотя вот эта строка if (!is_array($item)); становится бессмысленной.

if (!is_array($item));
                else $ret+=myCount($item);
				$ret++;

Теперь вопросы

Вот эта часть кода, как я понял перекладывает по одной ячейке из заданнго массива в новый и при каждом переложении увеличивает переменную cnt на 1, что и позволяет посчитать кол-во элементов в массиве. Правильно?

foreach($item as $v){
        $cnt++;

А вот этот проверяет, есть ли в переложенных элементах еще массив, и если есть присавивает $cnt = myCount($v, 1)+ $cnt, далее функция вызывает сама себя и вот тут я уже не понимаю, что она делает.

foreach($item as $v){
        if($mode==1 and is_array($v))
        $cnt += myCount($v, 1);
        $cnt++;

Вообще в идеале не мог бы ты написать как ведет себя эта функция на примере конкретного многомерного массива, как ты это сделал с факториалом:

fc(3) = 3*fc(2) = 3*2*fc(1) = 3*2*1*fc(0) = 3*2*1*1;

Так намного понятней. Заранее спасибо.

[K313]

Вторая функция - это то же самое что и первая!

Первая расчитывает факториал, вторая подсчитывает кол-во элементов в многомерном масиве И НИЧЕГО БОЛЬШЕ...

когда вы поймёте принцып работы первой функции вы сразу же поймёте и вторую.

[Int]

То, что стандартный count выдаёт другое значение, говорит только о том, что мы с разработчиком по-разному видим задачу:

array(1,2,3,array(10,12,array('a',1)));
разобьём на элементы: 1,2,3,10,12,a,1. Итого 7 штук, что моя программа и отобразила.

Программа работает так:
идёт цикл по массиву, каждый раз увеличивая счётчик на 1 или на результат обработки встреченного массива.
Сейчас буду писать элемент массива и в скобках значение счётчика:
[0]
1 (+1=1)
2 (+1=2)
3 (+1=3)
array()... заходим в массив (0)
	10 (+1=1)
	12 (+1=2)
	array... заходим в массив (0)
		'a' (+1=1)
		1 (+1=2)
		Возвращаем [2]
	(+2=4)
	Возвращаем [4]
(+4=7)
Возвращаем [7]

[4ak]

  On 3/1/2012 at 4:33 PM, Int said:

array(1,2,3,array(10,12,array('a',1)));

разобьём на элементы: 1,2,3,10,12,a,1. Итого 7 штук, что моя программа и отобразила.

Спасибо, разобрался, но насколько я понимаю элементов здесь все же 9, потому что массивы это тоже элемент и функция count как раз поэтому и считает 9.

Так более наглядно

$user = array (
                        1=>1
                        2=>2
                        3=>3
                        4=>array (
                                        1=>10
                                        2=>12
                                        3=>array(
                                                         1=>a
                                                         2=>1)

[Int]

Ну я видел это по-другому, поэтому реализовал тоже иначе. Как можно рассматривать массив в отрыве от его содержимого?

[MiksIr]

Большинство рекурсий можно безболезненно заменить циклом, чего вам и желаю

function factorial($n){
  $result = 1;
  for($i=$n;$i>0;$i--) {
    $result *= $n;
  }
  return $result;
}

[Int]

Если тема - изучение рекурсии, то заменять её циклом не целесообразно.

[4ak]

  On 3/1/2012 at 6:34 PM, MiksIr said:

Большинство рекурсий можно безболезненно заменить циклом, чего вам и желаю

function factorial($n){
  $result = 1;
  for($i=$n;$i>0;$i--) {
    $result *= $n;
  }
  return $result;
}

Я пока что не ищу легких путей, а просто изучаю php.

Но по вашему циклу я вижу, что не безболезненно Ваш цикл будет работать неправильно, потому что вы уменьшаете переменную $i, а результат увеличиваете в $n раз . Соответственно результат будет постоянно увеличиваться в $n раз и так будет происходить $i раз. То есть при $n=4 цикл выполнится 4 раза и $result будет равен 4*4*4*4= 256, в то время как факториал(4) равняется 24.

Если написать так for($n;$n>0;$n--) то все будет ок.

[MiksIr]

Ага, хотя на самом деле подразумевалось $result *= $i; Описался

На самом деле знать, что рекурсию можно часто заменить циклом очень важно. Ибо, во-первых, рекурсия не самый лучший прием программирования и его следует избегать. Во-вторых, просто помогает понять лучше - что такое рекурсия.

На практике, если говорить о PHP и веб-программировании, рекурсия применяется в случаях похожих на второй пример - когда у нас есть набор вложенных массивов (или объектов) неизвестной глубины, и нужно что-то сделать со всеми элементами этого массива. К слову, тоже можно решить циклом, но не сильно красиво.

Edited March 2, 2012 by MiksIr

[Great Rash]

Хорошим примером рекурсии может быть рисование фрактала. Вот где просто циклом точно не обойтись.

[4ak]

Я пока плохо представляю какой и для каких целей цикл или функцию использовать. Имеются мысли в сторону авторизации и тд., но не более.

На текущем этапе хочу хорошо разобраться в теории, чтобы была база и было проще в дальнейшем.

[Int]

Ну как для каких. Составь все перестановки букв некоторого слова.

Я так иногда анаграммы решаю, вывожу всё, что есть, потом ищу знакомые слова.

У нас как-то на городской олимпиаде было задание вывести все числа, получаемые из неповторяющихся цифр от 1 до n. Я сделал рекурсией, а кто-то сделал циклом от 1 до 12345...n и выводил те, которые не повторялись. Можно представить, сколько работала его программа. А моя сразу начинала вывод.

А ещё поиск пути в графе.