how can i understand which one is faster ??
It really does depend on a bunch of things, but recursion is theoretically slower. The slowerness can be one or both of too many recursive calls and the overhead of calling a function. Consider the basic fibonacci code in both recursion and iteration.
Code:
int recursive_fibonacci(int n)
{
if (n <= 1)
{
return n;
}
else
{
return recursive_fibonacci(n-1) + recursive_fibonacci(n-2);
}
}
int iterative_fibonacci(int n)
{
int a = 0;
int b = 1;
int c;
for (int x = 1; x <= n; ++x)
{
c = a + b;
a = b;
b = c;
}
return a;
}
The recursive version will be a lot slower because the recursive call tree grows exponentially. The iterative version has linear growth. This is where a recursive algorithm hides excessive function calls. Another example is factorials.
Code:
int recursive_factorial(int n)
{
if (n <= 1)
{
return 1;
}
else
{
return n * recursive_factorial(n-1);
}
}
int iterative_factorial(int n)
{
int x = 1;
while (n > 1)
{
x *= n--;
}
return x;
}
Both algorithms are linear, but the recursive one will be slower in theory because of the overhead for calling a function.
When it comes to Reckless vs. Cautious, Cautious is wrong in saying that Reckless' code does not count the digits. Reckless() can be proven to stop when val reaches 0, and for every recursive call, val is moved closer to 0.
As for which is faster, that would need testing. But even though both algorithms have O(N) growth, Cautious() is actually 2N vs. Reckless()'s N, plus Cautious() does more work in the loops. That might be enough to be slower than the overhead of recursive calls. I think Reckless() will be the faster of the two, and it is certainly the simpler one.
On a side note, both algorithms are wrong in that they do not handle negative numbers. Both algorithms are also I/O bound. Most of the time will be spent in printf() anyway, so quibbling about which algorithm is faster does not matter unless the growth factors are different.