Рекурсия. А нужно ли использовать?

AndreyD
AndreyD аватар
Offline
Зарегистрирован: 07.10.2018

Именно для программирования микроконтроллеров.

Можно же заменить циклами (ниже пример). Скорость та же. Ну кода побольше, зато рекурсия больше памяти "съедает".


// Функция рассчёта факториала рекурсией
uint32_t Fact1(uint32_t f) {
	if (f < 2) return 1; 
	return f * Fact1(f - 1);
}

// Функция рассчёта факториала циклом
uint32_t Fact2(uint8_t f) {
	if (f < 2) return 1;
	uint32_t rez = 1;
	for (uint8_t i = f; f > 1; f--) 
		rez *= f;
	return rez;
}

void setup()
{
	Serial.begin(9600);
	
	uint32_t rez;
	
	Serial.println(F("Расчёт факториала числа 30"));
	Serial.print(F("Через рекурсию: "));
	uint32_t start = micros();
	rez = Fact1(30);
	uint32_t duration = micros() - start;
	Serial.println(rez);
	Serial.print(F("Время расчёта: "));
	Serial.print(duration);
	Serial.println(F(" микросекунд"));

	Serial.println();
	Serial.print(F("Через цикл for:    "));
	start = micros();
	rez = Fact2(30);
	duration = micros()- start;
	Serial.println(rez);
	Serial.print(F("Время расчёта: "));
	Serial.print(duration);
	Serial.println(F(" микросекунд"));

}

void loop() {}

Результат:

Расчёт факториала числа 30
Через рекурсию: 1409286144
Время расчёта: 168 микросекунд

Через цикл for:    1409286144
Время расчёта: 168 микросекунд

 

rkit
Онлайн
Зарегистрирован: 23.11.2016

Обязательно. Иначе приедут из "управления К" и арестуют. Еще идиотские вопросы будут?

Lictor
Offline
Зарегистрирован: 01.10.2015

А такие расчеты при оптимизации во время компиляции кода не упрощаются до одинакового набора операций?

ЕвгенийП
ЕвгенийП аватар
Онлайн
Зарегистрирован: 25.05.2015

Её (как и всё остальное) нужно уметь готовить.

-NMi-
Offline
Зарегистрирован: 20.08.2018

А как это работает? А если взять количество итерацций больше ОЗУ это не сломается?

AndreyD
AndreyD аватар
Offline
Зарегистрирован: 07.10.2018

А да, переполнение uint32_t я не посмотрел, после 12! идут уже неверные результаты.

b707
Offline
Зарегистрирован: 26.05.2017

Андрей, рекурсия нужна не компьютеру, а программисту. Если рекурсия вам помогает - ее надо использовать, а если нет - то нет