How fast does the program/algorithm run? (recursive vs iterative)

hi all,
I have a question and I don't understand how these things can be determineted..I have read many things about recursive and iterative solutions and most of them are says that it depends on your code your compiler,your computer etc.. but in exams,
instructor can ask "me how fast does the program/algorithm run?" how can i understand which one is faster ?? for example fibonacci algorithms or base calculating algorithms..i guess recursive is faster in mathematical programs like fibonacci ?? is that true ?? here above one simple code..please can you give me explanation which one is faster and why ???
thank you..

Quote:

---

Professors Reckless and Cautious are having an argument about C functions that they both claim print the hexadecimal representation of positive integers:

Code:

---

  #define BASE 16


void Reckless(int val)
{
  int digit;
       
       
  if (val == 0)
  {
      /* do nothing */     
  }
  else
  {
      Reckless(val / BASE);
      digit = val % BASE;

      if ((digit >= 0) && (digit <=9))
        printf("%d", digit);
      else
        printf("%c", 55 + digit);
  }
       
}       


#define BASE 16


void Cautious(int val)
{     
  int remainder;
  int highDigitValue, numDigits, digit;
  int i;
   
       
    highDigitValue = 1; numDigits = 0;
    remainder = val;
   
    while (remainder != 0)
    {
      remainder = remainder / BASE;
         
      highDigitValue = highDigitValue * BASE;
      numDigits++;
    }
 
    remainder = val;
   
    highDigitValue = highDigitValue / BASE;
       
    for (i=0; i<numDigits; i++)
    {
      digit = remainder / highDigitValue;
         
      if ((digit >= 0) && (digit <=9))
          printf("%d", digit);
      else
          printf("%c", 55 + digit); 

      remainder = remainder - digit * highDigitValue;   
      highDigitValue = highDigitValue / BASE;
    }
}

---

Professor Cautious claims that his implementation is correct because his program first checks how many hexadecimal digits an integer values has and then prints these digits in the correct order. He further argues Professor Reckless’s implementation must be wrong because it does not count the number of hexadecimal digits. Professor Reckless, on the other hand, claims that there is no need to explicitly count the number of hexadecimal digits and therefore his recursive implementation is not only correct, but the program is much simpler and runs faster.

---

Come to think of it, noone knows which one will be faster. It all depends on the system it's running.

But your "Reckless" professor is correct. Why count the digits?! It doesn't make sense. By computations point of view, the "Reckless" approach is faster.

yes as i said in everywhere answer is same "no one knows which one will be faster"
and yes "Reckless" is correct.but why ? what is the exactly reason ?

so there is no way to know on paper "which one is faster"...this expression absolutely true whole conditions isn't it ???

Quote:

---

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.

It's the way recursive functions operate. Each time a function calls itself ( or any other ), information is saved on the stack untill the program flow returns there. That is why there is no need to explicitely count the digits.