Jump to content



Photo

Which Of These Is Faster?


  • Please log in to reply
8 replies to this topic

#1 flyingfisch

flyingfisch

    Casio Maniac

  • Deputy
  • PipPipPipPipPipPipPipPip
  • 1891 posts
  • Gender:Male
  • Location:OH,USA
  • Interests:Aviation, Skiing, Programming, Mountain Biking.

  • Calculators:
    fx-9860GII
    fx-CG10 PRIZM

Posted 05 December 2012 - 10:58 AM

Which of these loops is faster, and which would be preferred?

while 1 do
   --[[ ... ]]--
end

or

function something()
   --[[ ... ]]--
   something()
end


#2 Forty-Two

Forty-Two

    Casio Overlord

  • Deputy
  • PipPipPipPipPipPipPip
  • 528 posts
  • Gender:Male
  • Location:Well, The sign says "You are here"...

  • Calculators:
    Casio fx-CG10 Prizm
    Casio fx-9860GII
    TI-84+ SE

Posted 05 December 2012 - 08:02 PM

while 1. The recursive one will eventually give you a stack overflow.

#3 flyingfisch

flyingfisch

    Casio Maniac

  • Deputy
  • PipPipPipPipPipPipPipPip
  • 1891 posts
  • Gender:Male
  • Location:OH,USA
  • Interests:Aviation, Skiing, Programming, Mountain Biking.

  • Calculators:
    fx-9860GII
    fx-CG10 PRIZM

Posted 05 December 2012 - 10:08 PM

while 1. The recursive one will eventually give you a stack overflow.


Ah, ok. Is there any reason you would want to use the recursive one?

#4 MicroPro

MicroPro

    Casio Overlord

  • Deputy
  • PipPipPipPipPipPipPip
  • 640 posts
  • Gender:Male
  • Location:Iran

  • Calculators:
    Casio ClassPad 300

Posted 06 December 2012 - 07:36 PM

Even if program flow is interrupted before the stack fills up, the recursive one is slower because of the time spent during setting up the stack and stuff for calling/returning from the function.

On the other hand writing non-recursive code for solving some problems can be a pain, e.g Towers of Hanoi; in which recursive approach is preferred.

Source: textbook :P

#5 flyingfisch

flyingfisch

    Casio Maniac

  • Deputy
  • PipPipPipPipPipPipPipPip
  • 1891 posts
  • Gender:Male
  • Location:OH,USA
  • Interests:Aviation, Skiing, Programming, Mountain Biking.

  • Calculators:
    fx-9860GII
    fx-CG10 PRIZM

Posted 06 December 2012 - 08:06 PM

Even if program flow is interrupted before the stack fills up, the recursive one is slower because of the time spent during setting up the stack and stuff for calling/returning from the function.

On the other hand writing non-recursive code for solving some problems can be a pain, e.g Towers of Hanoi; in which recursive approach is preferred.

Source: textbook :P


Ah, ok, thank you for the clarification. :)

I have wondered about that for a while.

#6 Forty-Two

Forty-Two

    Casio Overlord

  • Deputy
  • PipPipPipPipPipPipPip
  • 528 posts
  • Gender:Male
  • Location:Well, The sign says "You are here"...

  • Calculators:
    Casio fx-CG10 Prizm
    Casio fx-9860GII
    TI-84+ SE

Posted 06 December 2012 - 10:38 PM

Also: many sorting algorithms use recursivity to partition data into smaller parts to sort (I believe quicksort and mergesort work like this).

#7 MicroPro

MicroPro

    Casio Overlord

  • Deputy
  • PipPipPipPipPipPipPip
  • 640 posts
  • Gender:Male
  • Location:Iran

  • Calculators:
    Casio ClassPad 300

Posted 21 December 2012 - 06:40 PM

Another case is when there is multiple recursive calls with the same inputs. For example write a non-recursive and a recursive function that generate Fibonacci numbers and compare the timings. How long do you think it will take for the recursive function to calculate the 50th number in the sequence?

#8 Forty-Two

Forty-Two

    Casio Overlord

  • Deputy
  • PipPipPipPipPipPipPip
  • 528 posts
  • Gender:Male
  • Location:Well, The sign says "You are here"...

  • Calculators:
    Casio fx-CG10 Prizm
    Casio fx-9860GII
    TI-84+ SE

Posted 25 December 2012 - 04:45 PM

It depends on the language, really. In some languages (lisp), the recursive solution is not only faster, but more elegant. In others (C, for example), it is easier to do it with a loop.

#9 MicroPro

MicroPro

    Casio Overlord

  • Deputy
  • PipPipPipPipPipPipPip
  • 640 posts
  • Gender:Male
  • Location:Iran

  • Calculators:
    Casio ClassPad 300

Posted 30 December 2012 - 01:19 PM

Lisp has complex compilation and optimization steps that turns the recursive code into hardware-friendly fast programs. In contrast, in most procedural languages, recursive function calls are compiled into "real" function calls which have much overhead for the program.

How long does it generating 50th Fibonacci number take in lisp?




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users