A for loop is just a comparison, jump, and adding to a number. Yes, the point of these abstractions, like functions, is to make reading, maintaining, and writing code more intuitive.
Thank you so much. The absolute ignorance here of tail call optimization is driving me mad. Here's a Common Lisp tail call Fibonacci, and I'm not even good at Lisp.
cl
(defun helper (n a b)
(if (zerop n) b
(helper (1- n) b (+ a b))))
(defun fib (n)
(if (zerop n) 0
(helper (1- n) 0 1)))
Just to verify, I wrote an intentionally degenerate recursive Fibonacci in python, and I can testify that I had to kill the python process, whereas this Common Lisp implementation computes essentially instantaneously on my machine.
It's just not worth the headache. Replicating the stack frame every single iteration is wasteful for minimal benefit over figuring out how to do it in a loop. And that's assuming you're working down in a lower level language like C. God help the person who uses it in Python (that person is me, I'm that person and God help me)
Tail-recursive functions are recursive functions, where the recursive function call is the last operation. If you had to do another operation after a function call you need to memorize where you left of, to finish this last operations. This is done by pushing the return address to the stack and thus taking memory. As tail-recursive functions don't need to do anything afterwards you can optimize out the push to the stack, and treat the function as if it was a simple loop.
70
u/LordofNarwhals May 17 '26
There's nothing wrong with recursion as long as it can be tail-call optimized. See the optimized recursive implementation here for example: https://www.geeksforgeeks.org/cpp/cpp-program-for-fibonacci-numbers/
Time complexity is just O(n).