8 replies to this topic

[flyingfisch]

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

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

or

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

[Forty-Two]

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

[flyingfisch]

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?

[MicroPro]

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

[flyingfisch]

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

Ah, ok, thank you for the clarification.

I have wondered about that for a while.

[Forty-Two]

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

[MicroPro]

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?

[Forty-Two]

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.

[MicroPro]

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?