взятие остатка по модулю

[whtfng]

есть небольшая программка, выполняющая взятие остатка по модулю

#include "stream.h"
int mod (int a, int b) {
return b == 0 ? a : mod (b, a % b);
}

int main() {
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", mod (a, b));
return 0;
}

как понять, сколько раз будет вызвана функция mod???

[p51x]

Вставить статический счетчик, прикинуть по алгоритму руками.

[whtfng]

а что значит "прикинуть руками"? как раз и хотелось бы понять на живом примере как работает алгоритм, по идее тут рекурсия пока b не равно нулю.

ps: а счетчик прикрутил, как-то так:

#include <stdio.h>
int mod (int a, int b, int n) {
n++;
if (b == 0)
{
printf ("mod counts %i times(à)\n", n);
return a;
}
else
return mod(b, a%b, n);
}

int main() {
int a, b;

scanf("%d%d", &a, &b);
printf("%d\n", mod (a, b, 0));

getchar();
getchar();

return 0;
}

[whtfng]

только все равно не понятно по какому принципу вызывается mod?
пусть a=7, b=2, счетчик выдает mod counts 3 times.

[Tirendus]

#include <iostream>

int mod (int a, int b, int &count) {
	count++;
	std::cout << count << " ";
	return b == 0 ? a : mod (b, a % b, count);
}

int main() {
	int a, b, n = 0;
	scanf("%d%d", &a, &b);
	printf("%d\n", mod (a, b, n));
	std::cout << n;
	return 0;
}

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