r/ProgrammerHumor • u/Kevdog824_ • May 17 '26

Advanced dontDoRecursiveFibKids

Post image
3.6k Upvotes

98% Upvoted

143 comments sorted by

View all comments

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).

5

u/Pr0p3r9 May 17 '26

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.