# Transforming Nested Loops into a Single Loop with State

DevFeed: [Transforming Nested Loops into a Single Loop with State](<https://devfeed.tech/articles/loopy-21790.md>)

Original publisher: [Read original article](<http://blog.cleancoder.com/uncle-bob/2020/09/30/loopy.html>)

Published: 2020-09-30T00:00:00Z

Content type: tutorial

Language: en

Sources: [Robert C. Martin](<https://devfeed.tech/sources/robert-c-martin.md>), [The Clean Code Blog](<https://devfeed.tech/sources/the-clean-code-blog.md>)

Topics: [Code](<https://devfeed.tech/topics/code.md>), [Clojure](<https://devfeed.tech/topics/clojure.md>), [Finite-state machine](<https://devfeed.tech/topics/finite-state-machine.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [clojure](<https://devfeed.tech/tags/clojure.md>), [code](<https://devfeed.tech/tags/code.md>), [flow](<https://devfeed.tech/tags/flow.md>), [go](<https://devfeed.tech/tags/go.md>), [i](<https://devfeed.tech/tags/i.md>), [journey](<https://devfeed.tech/tags/journey.md>), [loops](<https://devfeed.tech/tags/loops.md>), [machine](<https://devfeed.tech/tags/machine.md>), [model](<https://devfeed.tech/tags/model.md>), [state](<https://devfeed.tech/tags/state.md>)

## AI overview

This article compares the standard Java solution to the Prime Factors Kata with a Clojure implementation using a single recursive loop. It then shows how nested-loop behavior can be represented with state and transformed into a single loop, culminating in a Moore model finite-state machine.

## Source excerpt

The following is a segment of a journey. It has no obvious beginning point, nor does it actually end up anywhere. The value, if any, is in the journey itself. The code below is the standard solution to the Prime Factors Kata. public List<Integer> factorsOf(int n) { ArrayList<Integer> factors = new ArrayList<>(); for (int d = 2; n > 1; d++) for (; n % d == 0; n /= d) factors.add(d); return factors; } However, I was doing this kata in Clojure the other day and I wound up with a different solution. It looked like this: (defn prime-factors [n] (loop [n n d 2 factors []] (if (> n 1) (if (zero? (mod n d)) (recur (/ n d) d (conj factors d)) (recur n (inc d) factors)) factors))) The algorithm is pretty much the same. I mean if you tracked the value of n, d, and factors they would go through the same changes. On the other hand the code in Java is a doubly nested loop; but the code in Clojure is a single recursive loop with two recursion points. That's interesting. I could write the recursive algorithm in Java like this: private List<Integer> factorsOf(int n) { return factorsOf(n, 2, new ArrayList<Integer>()); } private List<Integer> factorsOf(int n, int d, List<Integer> factors) { if (n>1) { if (n%d == 0) { factors.add(d); return factorsOf(n/d, d, factors); } else { return factorsOf(n, d+1, factors); } } return factors; } And then, since this is tail recursive, I could rewrite it as a straight loop. private List<Integer> factorsOf(int n, int d, List<Integer> factors) { while (true) { if (n > 1) { if (n % d == 0) { factors.add(d); n /= d; } else { d++; } } else return factors; } } For all intents and purposes this code executes the same algorithm as the standard solution; but it does not have a doubly nested loop. We have transformed the code from a doubly nested loop, to a single loop, without affecting the algorithm. Is this always possible? In other words: given a program with a nested loop, is there a way to write the same program with a single loop? The answer to that is