Suggest an editImprove this articleRefine the answer for “Replacing recursion with a loop”. Your changes go to moderation before they’re published.Approval requiredContentWhat you’re changing🇺🇸EN🇺🇦UAPreviewTitle (EN)Short answer (EN)**Almost any recursion can be rewritten as a loop: you just replace the self-call with repeating the same actions while changing the state.** Recursion consists of a base case (return a result without a new call) and a recursive step (the function calls itself with new arguments). To turn that into a loop, the function arguments become local variables, the recursive call becomes a `while` or `for` iteration, and the base case becomes the exit condition. A loop is usually more efficient because it does not spend a call stack frame on every level, but recursion is often logically clearer for nested structures such as trees. ```javascript // recursive function factorial(n) { if (n === 1) return 1; return n * factorial(n - 1); } // iterative function factorialIterative(n) { let result = 1; while (n > 1) { result *= n; n--; } return result; } ``` **Key point:** move the state into variables, turn the base case into an exit condition, turn the self-call into an iteration.Shown above the full answer for quick recall.Answer (EN)Image**Almost any recursion can be rewritten as a loop if you carefully replace the self-call with repeating actions that change some state.** A recursive call carries its state in the function arguments, while a loop carries the same state in ordinary variables, so the translation between them is mechanical. ## Theory ### TL;DR - Recursion always consists of two parts: a base case and a recursive step. - To get a loop, create variables for the state (the former arguments). - Repeat the steps with `while` or `for`. - Break out of the loop where the recursion would have hit its base case. - Loops are usually more efficient: less memory, faster, no risk of a blown stack. - Recursion can be logically clearer, especially for nested structures such as trees. ### Quick example ```javascript // Recursive version function factorial(n) { if (n === 1) return 1; return n * factorial(n - 1); } // Iterative version function factorialIterative(n) { let result = 1; while (n > 1) { result *= n; n--; } return result; } console.log(factorial(5)); // 120 console.log(factorialIterative(5)); // 120 ``` We simply "unrolled" the recursion: instead of many function calls we change `n` inside the loop. ### The general principle Recursion normally consists of: 1. a **base case**, where we return a result without a new call; 2. a **recursive step**, where the function calls itself with new arguments. To turn that into a loop: - create variables for the state (that is, for the arguments); - repeat the steps with `while` or `for`; - break out once the base case is reached. Put differently, recursion keeps its state on the call stack, while a loop keeps the same state in local variables. All the work of rewriting comes down to finding that state and making it explicit. ### Example: array sum Recursion: ```javascript function sum(arr, i = 0) { if (i === arr.length) return 0; return arr[i] + sum(arr, i + 1); } ``` Loop: ```javascript function sumIterative(arr) { let result = 0; for (let i = 0; i < arr.length; i++) { result += arr[i]; } return result; } ``` The pattern is easy to see here: the index `i` used to be a recursion argument and became the loop counter. The accumulator `result` replaced the chain of additions that previously "waited" on the stack until the deepest call returned. ### Example: Fibonacci numbers Recursive: ```javascript function fib(n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } ``` Iterative: ```javascript function fibIterative(n) { let a = 0, b = 1; for (let i = 2; i <= n; i++) { [a, b] = [b, a + b]; } return b; } ``` Here the loop is **far more efficient**: the naive recursion performs exponentially many calls because it recomputes the same values over and over, while the loop runs only `n` iterations and keeps two numbers in memory. ### The general conversion template | Recursion element | In a loop | | --- | --- | | Function arguments | Local variables | | Recursive call | Loop iteration | | Base case | Exit condition (`if`, `while`) | | Returning a value | Return after the loop | The order of steps is always the same: identify the base case and turn it into an exit condition, move the state into variables, and change them on every iteration. ### When to pick a loop and when recursion - Any recursion can be written as a loop if you identify the base case, move the state into variables and change them on each iteration. - Loops are usually **more efficient**: less memory, faster, no `RangeError: Maximum call stack size exceeded`. - Recursion can be **clearer logically**, especially for nested structures (trees or the DOM, for example). - When the recursion branches (as a tree traversal does), a simple counter is no longer enough: the state moves into an explicit stack array. ```javascript // Tree traversal without recursion: our own stack instead of the call stack function collectValues(root) { const out = []; const stack = [root]; while (stack.length > 0) { const node = stack.pop(); if (!node) continue; out.push(node.value); for (const child of node.children ?? []) stack.push(child); } return out; } ``` ### Common mistakes - **Forgetting the exit condition.** Recursion without a base case throws `RangeError`, while a loop without an exit condition simply freezes the tab forever, which is harder to notice. - **Not changing the state inside the loop body.** If you forget `n--` or `i++`, the condition never becomes false. - **Mixing up the order of computation.** The recursion `n * factorial(n - 1)` multiplies on the way back up the stack, so when rewriting it as a loop you must watch which side the result accumulates from. - **Assuming recursion is always slower.** It is not inherently slow: what makes the naive `fib` slow is recomputing the same values, not recursion itself. With memoization the recursive version is linear too. - **Rewriting as a loop something that reads better recursively.** For trees and graphs a loop with an explicit stack is often longer and more confusing than three lines of recursion.For the reviewerNote to the moderator (optional)Visible only to the moderator. Helps review go faster.