Малко рекурсия

Време е да дам и последните две задачки по Синтез и анализ на алгоритми – това са два прости примера от областта на рекурсията.

Задача 1: Да се изведат в обратен ред стойностите на едномерен масив.

#include <iostream>
using namespace std;

int arr[] = { 5, 4, 3, 2, 1 };

void izvedi(int arr[], int ndx){
	cout << arr[ndx] << endl;
	if(ndx > 0) izvedi(arr, --ndx);
}

int main(){
	int size=5;
	izvedi(arr, --size);
	return 0;
}

Какво става: имаме функция, на която подаваме масив и номер на негов елемент, който искаме да изведем. Функцията извежда стойността на този елемент и вика себе си, подавайки същия масив и номера на предишния елемент. И така, докато стигнем нулевия елемент…

Задача 2: Да се изведе сумата на цифрите на естествено число.

#include <iostream>
using namespace std;

int poedno(int a){
	if (a) return a%10 + poedno(a/10);
}	

int main(){

	cout << poedno(1234);
	return 0;
}

Съвсем просто. На входа на функцията имаме число и ако то не е нула, извеждаме остатъка от делението на десет (т.е. последната му цифра) и викаме същата функция с аргумент частното на числото и 10.

Това е всичко. От домашното ни остана само една точка – съпоставка на сортиращите алгоритми. Но това следващия път…