No body will persuade me that trivial: code + stack push + recursive call is faster than code +loop jump. It is simply impossible.
Well, perhaps more detailed analysis is in order. Here's the meat of the recursive version of decout:
void decout(int n) {
{
int rem = n % 10; // extract the least significant digit of the number.
n /= 10; // remove that digit from the overall number
if (n > 0) { // If there are any more digits in the number
decout(n); // Then print them first
}
putchar(rem + '0'); // Convert the digit to ascii and print
}And one of the non-recursive versions (also trimmed):
void print_dec_2(int n) {
do {
unsigned int t = u/10;
digits[i++] = u % 10;
u = t;
} while(i<10 && u != 0);
while(i) {
putchar(digits[--i]+'0');
}
}Notice that the recursive version does not contain ANY loops or any explicit stores. Essentially, each loop iteration branch that needs to be done by the non-recursive version is replaced by a call or return (BL or pop of sp) (which takes the same time, probably), and each store/retrieval of a character to the buffer in non-recursive is replaced by a POP (which also takes the same time.) The recursive version may lose a bit of time doing the sign check each time, and the non-recursive version may lose a bit by having to maintain its own counter or pointer, but at some fundamental level they are doing exactly the same thing - N multiplies/divides, M adds/subtracts, O loads and stores, and P branches. As the assembly dumps show, the compiler optimizes the recursive version sufficiently that it does not need any "extra" data saved on the stack, other than the PCs and the extra bytes in each digit.
We're down to experimental error.
Indeed. Thanks to Bruce for doing the grunt-work. This is not supposed to show that recursion is always "better" in any way than an iterative method; but it DOES show that recursion is not necessarily extremely expensive, either.
You can usually add saving the base pointer to that stack too
Doesn't happen in this case. Compilers have gotten very good at not creating "stack frames" when they're not needed, and CPU/ABI combinations have gotten pretty good at ensure that simple functions don't usually need them.
2. You always check value is negative.
I'll give you that one. But this is a micro-optimization...
1. You always send unsigned value in every call but first time. Internal conversion from signed to unsigned all the time.
signed/unsigned is usually not an actual conversion, but more a signal to the compiler on how to treat condition flags. So these "casts" don't actually add any instructions or execution time.
3. Every recursion put on stack all variables. You spend more of the memory
As shown above, in this example "all of the variables" consists only of the extracted digit, which you'd have to save somewhere anyway.
wrong type for ch and implicit conversion may cost you some large percentage of speed!Show me where in the assembly language, please (see (1) above.) The use of int vs char for the individual digits is an "interesting" optimization - on most 8bit CPUs (maybe including x86), using char would be desirable to save registers and possible compute time in multiply/divide. On most 32bit RISC CPUs (and ARM in particular), using "int" probably avoids un-needed "covert word to byte" instructions.
(There ought to be some "rule" that distinguishes between variables that would have to be saved anyway, and variables that are local (in a stack frame, or in registers that need saving) but not actually part of the "recursive context." Functions that have much more local context than recursive context would be poor candidates for recursion.)
(It's worth noting that the analysis above loses validity on other CPUs, where "call" and "branch" do NOT have the same cost. On bigger AVRs, call and return each take 4 cycles, and branches only 1 or 2. OTOH, an AVR could store each digit in only a single byte on the stack, with the "push" being significantly cheaper than storing to local variables.)
The USUAL excuse for recursion is that it makes the code much simpler, more compact, and easier to understand at the SOURCE CODE level. That's vaguely true in this example ("print the rest of the number, print the last digit" vs "extract all the digits and print them backwards"), and not really true at all for the factorial/fibonacci examples. But it gets real obvious when trying to do trees or divide-and-conquer sort algorithms without recursion. Towers of Hanoi is probably a good example - anyone want to turn this Hanoi code into an iterative version?
void hanoifun(int n, char fr, char tr, char ar)//fr=from rod,tr =to rod, ar=aux rod
{
if (n == 1)
{
printf("\n Move disk 1 from rod %c to rod %c", fr, tr);
return;
}
hanoifun(n-1, fr, ar, tr);
printf("\n Move disk %d from rod %c to rod %c", n, fr, tr);
hanoifun(n-1, ar, tr, fr);
}
Home
Help
Search
Login
Register
Poll
