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