Рекурсия С++

[little_greg]

Объясните, пожалуйста, принцип работы рекурсивной функции - какая из функции и когда вызывается

factorial(int val = 5) // условно функция 1

{

if (val > 1)

return val * factorial(val - 1); // условно функция2

return 1;

}

заранее спасибо

[Тролль]

little_greg:

Это обычное описание функция, просто "функция1" - объявление ее названия, а "функция2" - ее вызов самой из себя. Функция - это кусок кода. Из его середины вполне можно передать управление снова на начало этого куска кода, а после его выполнения возвратиться к прерванному выполнению первого прохода по коду. Это суть рекурсии. Функции, которые в процессе выполнения вызывают сами себя, называются рекурсивными.

Но при построении кода рекурсивной функции компилятором есть одно осложнение - при повторном пробеге по коду функции бывшие ранее значения переменных будут затерты новыми значениями. А старые значения еще будут нужны для продолжения прерванного ранее первого прохода. Поэтому при переходе к началу кода функции из его середины надо значения внутренних переменных где-то запомнить, а потом при возврате к продолжению первого прохода по коду функции - восстановить. Такое запоминание (в стеке) и последующее восстановление для рекурсивных функций компилятор вставляет автоматически.

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

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

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

Функция факториал, при аргументе, скажем, 6, во время выполнения вызывает сама себя (то есть функцию факториал с параметром 5, а та во время своего выполнения - ту же функцию факториал с параметром 4 и так далее пока не дойдет до значения 1 - так как функция факториал написана так, что при значении 1 сама себя больше не вызывает, а просто передает 1 в вызвавший ее экземпляр функции факториал в точку, откуда была вызвана. Прерванное в этой точке выполнение кода продолжается, доходит до конца, выработанное значение снова передается в точку прерывания выполнения предыдущего вызова функцией самой себя и так до тех пор, пока мы снова не всплывем на самый верхний уровень и благополучно закончим начальный вызов рекурсивной функции, когда ее еще вызвала другая функция, а не она сама себя.

Еще одно замечание - вызов типа sqrt(sqrt(x)) не требует рекурсии, поскольку значение внутреннего sqrt вычисляется еще до начала выполнения внешнего sqrt. Никакого прерывания выполнения кода функции sqrt тут не требуется.

Изменено 29 сентября, 2009 пользователем Тролль

[Lion HC]

// Припустим мы визвали откуда-то функцию factorial (без явно заданого параметра)....factorial(int val = 5) // без явно заданого параметра val = 5//...начинается виполнение первой функции....{if (val > 1)					 // val = 5return val * factorial(val - 1); // здесь выполнение первой функции приостанавливается{							 // и запускается рекурсивная копия функции factorial уже с параметром 5-1if (val > 1)						// val = 4return val * factorial(val - 1);	// здесь выполнение второй функции приостанавливается и визивается рекурсия...	{								if (val > 1)						// val = 3	return val * factorial(val - 1);	//		{									if (val > 1)						// val = 2		return val * factorial(val - 1);	//  			{										if (val > 1)						// val = 1			return val * factorial(val - 1);	// оператор не виполняется в силу невиполнения условия 			return 1;							// последняя рекурсия возвращает 1 в предпоследнюю рекурсию			}		return 1;							//		}	return 1;							//	}return 1;							// }return 1;						 // }

[little_greg]

всем спасибо!

[stalker7438]

последние строки должны выглядеть немного по-другому:

return 1;

return 2;

return 6;

return 24;

return 120;