Fibonacci tail recursion in JavaScript and Clojure. Conversion from iteration to recursion is done in the same ways as the basic conversion. Some steps are skipped to make the conversion concise.
// Recursion, but not tail call. Simple and easy to understand, but very slow.
// Note that negative numbers are not handled correctly to make it simpler throughout this post.
function fib(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
function fib(n) {
let curr = 0;
let next = 1;
let i = 1;
while (i <= n) {
let prev = curr;
curr = next;
next = prev + curr;
i++;
}
return curr;
}
// - move loop condition to inside of while
// - return termination case early
// - use destructuring to assign variables
// - make index descreasing
function fib(n) {
let [i, curr, next] = [n, 0, 1];
while (true) {
if (i <= 0) return curr;
[i, curr, next] = [i - 1, next, curr + next];
}
}
function fib(n) {
let [i, curr, next] = [n, 0, 1];
loop: while (true) {
if (i <= 0) return curr;
[i, curr, next] = [i - 1, next, curr + next];
continue loop;
}
}
function fib(n) {
const loop = (i, curr, next) => {
if (i <= 0) return curr;
return loop(i - 1, next, curr + next);
}
return loop(n, 0, 1);
}
function fib(n, curr = 0, next = 1) {
if (n <= 0) return curr;
return fib(n - 1, next, curr + next);
}
const fib = (n, curr = 0, next = 1) => n <= 0 ? curr : fib(n - 1, next, curr + next);
;;; Note that the condition is flipped from the JS version above.
(defn fib
([n] (fib n 0 1))
([n curr next] (if (pos? n) (recur (dec n) next (+ curr next)) curr)))
(defn fib [n]
(loop [i n, curr 0, next 1]
(if (pos? i) (recur (dec i) next (+ curr next)) curr)))
Published: 2024-06-17
Tagged: clojure fp programming javascript
Converting very basic loop to tail recursion using JavaScript and Clojure at the end.
// Sum integer from 1 to n (inclusive).
function sumTo(n) {
let res = 0;
for (i = 1; i <= n; i++) {
res += i;
}
return res;
}
// For-loop is a syntactic sugar for while loop.
// Any for-loop can be changed to while loop.
function sumTo(n) {
let res = 0;
let i = 1;
while (i <= n) {
res += i;
i++;
}
return res;
}
// We can move the condition of while loop to inside the loop with break
function sumTo(n) {
let res = 0;
let i = 1;
while (true) {
if (i <= n) {
res += i;
i++;
} else {
break;
}
}
return res;
}
function sumTo(n) {
let res = 0;
let i = 1;
while (true) {
if (i > n) {
return res
}
res += i;
i++;
}
// This is unreachable, return statement here can be removed
}
function sumTo(n) {
let res = 0;
let i = n;
while (true) {
if (i <= 0) {
return res;
}
res += i;
i--;
}
}
function sumTo(n) {
let [res, i] = [0, n];
while (true) {
if (i <= 0) {
return res;
}
[res, i] = [res + i, i - 1];
}
}
function sumTo(n) {
let [res, i] = [0, n];
loop: while (true) {
if (i <= 0) {
return res;
}
[res, i] = [res + i, i - 1];
continue loop; // Sure, this is unnecessary, but added for the next step
}
}
function sumTo(n) {
let [res, i] = [0, n]; // Initialization. These will be the initial value for the inner recursion function
loop: while (true) { // This will become the inner recursion function which take (res, i) as parameters
if (i <= 0) { // termination condition of the recursion
return res;
}
[res, i] = [res + i, i - 1]; // These are the new values of res and i when not terminated.
// These will be carried to the next step (recursive call).
continue loop; // This will be recursive call with new params from the above line
}
}
function sumTo(n) {
// Inner function for tail recursion.
const loop = (res, i) => {
if (i <= 0) { // Same termination condition. No need to change
return res;
}
// Recursive call with values for next step.
return loop(res + i, i - 1);
}
// Delegate to inner function with the params same as the initial values of the loop version.
return loop(0, n);
}
function sumTo(n) {
const loop = (i, res) => {
if (i <= 0) {
return res;
}
return loop(i - 1, res + i);
}
return loop(n, 0);
}
// Initial value of the previous version is set as the default value of res.
// Since the inner function (loop) is removed, sumTo will be directly called.
// We don't need variable i anymore. It is replaced by n.
function sumTo(n, res = 0) {
if (n <= 0) {
return res;
}
return sumTo(n - 1, res + n);
}
const sumTo = (n, res = 0) => (n <= 0) ? res : sumTo(n - 1, res + n);
;;; Clojure doesn't support default parameters.
;;; Multi-arity function can be used instead of inner function.
;;; In clojure, recur needs to be used to perform tail recursion with tail-call optimization.
(defn sumTo
([n] (sumTo n 0)) ; call with res = 0
([n res]
(if (<= n 0) ; termination condition
res ; return res when terminated
(recur (dec n) (+ res n))))) ; recursive case
;;; Loop macro can be used to have tail recursion in the middle of the function.
(defn sumTo [n]
;; initialize the loop with i to n and res to 0
;; this becomes the target for recur below
;; comma is unnecessary, but added for clarity
(loop [i n, res 0]
(if (<= i 0) res (recur (dec i) (+ res i)))))
Published: 2024-06-07
Tagged: clojure fp programming javascript
I have worked at a company and on a team where Optional is used extensively for a long time. So, I was very surprised when I found out that Optional is a controversial topic. There is even a camp that believes Optional should be avoided. Brian Goetz, the Java Architect, explicitly advocates the "Use Optional as a Return Value in Limited Cases" camp on Stack Overflow. This Stack Overflow post was written in 2014, and comments are still active even in 2024.
All this controversy confused me a lot. My current team follows Brian Goetz's opinion, and it is not very easy to persuade them to use Optional more broadly whenever needed.
Then, I found this comment in Brian Goetz's post, and my mind became clear:
Yes,Java did not invent Optional. Neither does Java's Optional type do anything special than its usage in other languages.
Optional (or Option or Maybe) probably predates Java. Java users used custom Optional types (e.g., Guava) even before java.util.Optional was added. The opinion of the Java Architect doesn't need to be considered the golden rule in this case. Actually, there are other opinions even within the Java core team as mentioned here.I know that Java Optional has issues. It has memory overhead. It can make code look uglier. It is sometimes not very ergonomic to use. It is not very well integrated with older Java libraries.
However, it is still Java's best weapon against NullPointerException.
Published: 2024-05-29
Tagged: java programming