3 ms·

Yes, also the author is wrong — in FP the direct equivalent of a loop are tail recursive functions (i.e. you can take any loop and transform it into a tail recu

Yes, also the author is wrong — in FP the direct equivalent of a loop are tail recursive functions (i.e. you can take any loop and transform it into a tail recursion) and not "list processing". Here's Scala: def fib(n: Int, a: Int, b: Int): Int = { if (n > 0) fib(n - 1, b, a + b) else a } Unfortunately Java cannot express self tail recursive functions and Scala too can't express mutual tail recursive functions, as that would require runtime support. But you know what? That mutable loop is totally fine, because any mutation it has is encapsulated, the function itself being pure.

epai 9y ago
Just to expand a little on the "you can take any loop and transform it into a tail recursion" (because I think it's cool), here's an example: Python iterative solution 1. def fib(n): 2. i, curr, next = 0, 0, 1 3. while i < n: 4. i += 1 5. curr, next = next, curr + next 6. return curr Python tail-recursive solution* 1. def fib(n): 2. def fib_tail(i, curr, next): #1 3. if i >= n: #2 4. return curr #3 5. return fib_tail(i+1, next, curr+next) #4 6. return fib_tail(0, 0, 1) Some explanation of the 1-1 conversion process: #1. We need a helper function, `fib_tail` to keep track of the variables we update in the while loop. (lines 4-5 in iterative) #2-3. Return `curr` when the opposite of the while condition is met. (lines 3,6 in iterative) #4. Recursively call `fib_tail`, using same update logic as while loop body when passing arguments. (line 5 in iterative) #5. Call helper function with initial values for the additional variables (line 1 in iterative) * We're going to pretend that Python supports tail recursion. It doesn't, but I figure more people are familiar with python; think of it more as pseudocode for instruction. You could easily implement the above in something like Scheme

epai 9y ago

Just to expand a little on the "you can take any loop and transform it into a tail recursion" (because I think it's cool), here's an example: Python iterative solution 1. def fib(n): 2. i, curr, next = 0, 0, 1 3. while i < n: 4. i += 1 5. curr, next = next, curr + next 6. return curr Python tail-recursive solution* 1. def fib(n): 2. def fib_tail(i, curr, next): #1 3. if i >= n: #2 4. return curr #3 5. return fib_tail(i+1, next, curr+next) #4 6. return fib_tail(0, 0, 1) Some explanation of the 1-1 conversion process: #1. We need a helper function, `fib_tail` to keep track of the variables we update in the while loop. (lines 4-5 in iterative) #2-3. Return `curr` when the opposite of the while condition is met. (lines 3,6 in iterative) #4. Recursively call `fib_tail`, using same update logic as while loop body when passing arguments. (line 5 in iterative) #5. Call helper function with initial values for the additional variables (line 1 in iterative) * We're going to pretend that Python supports tail recursion. It doesn't, but I figure more people are familiar with python; think of it more as pseudocode for instruction. You could easily implement the above in something like Scheme