Previous: Functional Programming dialogue for front-end Engineers – 1
Day 2: Recursion & tail recursion
Student: Good morning, fang. What’s on today?
Today we will talk about recursion and tail recursion
Student: When will data be immutable?
Fang: No hurry, data immutable is throughout, don’t talk about it in particular.
Student: Oh…
Let me write a recursive factorial:
f = n => {
if(n<=1) {
return 1
} else {
return n * f(n-1)
}
}
Copy the codeThen use the “substitution method” to calculate f(4) :
f(4)
= 4 * f(3)
= 4 * (3 * f(2))
= 4 * (3 * (2 * f(1)))
= 4 * (3 * (2 * 1))
= 4 * (3 * 2)
= 4 * 6
= 24
Copy the codeNote the “shape” of the calculation, which looks like a greater than sign (>) :
First recursion, then recursion.
Student: That’s another way of thinking about recursion. Can I think that “recursion” is the process of calling the stack and “return” is the process of bouncing the stack?
Fang: Yes, but not completely. As I mentioned earlier, some languages don’t have a call stack, so stack-popping is just one way to implement recursion, even though it is very popular.
Student: What about pseudo recursion?
Fang: Let me give you an example first. It’s simpler than factorial
Print = (n) => {if(n===0){return} console.log(n) return print(n-1)Copy the codeThen use the “substitution method” to calculate print(4) :
Print (4) = print(3) = print(2) = print(1) = endCopy the codeNote that the shape of this calculation is “a straight line” :
Student: Is that also recursion?
Fang: Yes and no.
Student: How?
Fong: If you asked about the Chinese concept of “recursion”, this calculation does not involve “recursion” and “return”, so it is not recursive.
Student: No recursion at all.
Fong: But if you’re asking about recursion, then this calculation is repeating print calls over and over again, so it’s recursion.
Student: You mean recursion is a problem? Should it be translated as “reappear”?
Fang: I dare not say so. But for accuracy, we use “recursion” for a recursion that computs a greater than sign and “tail recursion” for a recursion that computs a straight line. The code characteristic of “tail recursion” is that recursion occurs at the end of the code (the tail bit)
Student: It was the tail of the tail. I thought it was fake in disguise.
Fang: Did I not make it clear?
Student: So why is return n * f(n-1) not tail recursion? Isn’t f(n-1) in the last sentence?
F (n-1) is the second to last step, not the last step, so it is not tail recursion.
Student: I see. So the advantage of tail recursion is that you don’t have to go back?
Fang: You can understand it this way.
Student: But what about the factorial of the tail recursion? I can’t think of anything
Fang: Ask me more and you can write it out. I’ll write one for you first
f = (n, result = 1) =>
n > 1 ? f(n-1, result * n) : result
Copy the codeRun it in:
F (4) = f(3, 4) = f(2,12) = f(1,24) = 24Copy the codeLook, is this line straight?
Student: Ah, you passed the result of the previous step as a parameter to the next call in order not to “return”
Fang: that’s right.
Student: I didn’t think of that.
Fang: You’ll see later.
Student: What about complex recursion? Can I write tail recursion? Like Fibonacci:
fib = (n) =>
n === 0 ? 0 :
n === 1 ? 1 :
fib(n-1) + fib(n-2)
Copy the codeThe process for finding fib of 4 looks like this:
Fib (4) = f (3) + f (2) / / abbreviated to f = (f (2) + f (1)) + (f (1) + f (0)) = ((f (1) + f (0)) + f (1)) + (f (1) + f (0)) = ((f (1) + f (0)) + f(1)) + (1 + 0) = ((f(1) + f(0)) + f(1)) + 1 = ((f(1) + f(0)) + 1) + 1 = ((1 + 0) + 1) + 1 = (1 + 1) + 1 = 2 + 1 = 3Copy the codeThis is a bad recursion to write tail recursion, right?
Fang: Just use your brain a little bit.
fib = (n, prevResult = 0, result = 1) =>
n === 0 ? prevResult :
n === 1 ? result :
fib(n - 1, result, prevResult + result)
Copy the codeLet’s evaluate fib of 4:
fib(4)
= fib(3, 1, 1)
= fib(2, 1, 2)
= fib(1, 2, 3)
= 3
Copy the codeIsn’t that all right?
Student: Good boy! You pass the last two values as arguments to the next call. Your n is just for counting, and when n equals 1 you return the last result!
Fang: yes! Isn’t that easy?
Student: So… That…… Is there a tail recursion for quicksort?
Fang: Yes, there is, but I’m afraid you can’t understand it, so I put the “recursive version” you wrote yesterday here:
/*1*/ quickSort = (array) => {
/*2*/ if(array.length <= 1) {return array}
/*3*/ let [pivot, ...rest] = array
/*4*/ let small = rest.filter(i => i<=pivot)
/*5*/ let big = rest.filter(i => i>pivot)
/*6*/ return [...quickSort(small), pivot, ...quickSort(big) ]
/*7*/ }
Copy the codeThere are two problems with writing tail recursion:
- After quickSort(small) you have to go back to quickSort(big)
- After quickSort(big) is done, you must go back and splice quickSort(small), Pivot, and quickSort(BIG) together
Isn’t it?
Student: Yeah, it seems impossible to compute the result ahead of time and pass it on to the next function call. I doubt you can do tail recursion this time
Fang: Then don’t calculate the result in advance, don’t settle
Student: What do you mean not working out the results in advance?
Fang: Let’s look at the code:
/*1*/ qs = (array, next) => { /*2*/ if(array.length <= 1) { return next(array)} /*3*/ const [pivot, ...rest] = array /*4*/ const small = rest.filter(i=>i<=pivot) /*5*/ const big = rest.filter(i=>i>pivot) /*6*/ qs(small, (sortedSmall)=>{ /*7*/ qs(big, (sortedBig)=>{ /*8*/ next([...sortedSmall, pivot, ... sortedBig])})})} qs (,10,5,2,7,3,8,4,9,6 [1], (result) = > {the console. The log (result)}) / / output [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]Copy the codeThe first five lines are unchanged; you focus on lines 6 to 8.
Student: Boy, did you take the original
/*4*/ let small = rest.filter(i => i<=pivot)
/*5*/ let big = rest.filter(i => i>pivot)
/*6*/ return [...quickSort(small), pivot, ...quickSort(big) ]
Copy the codeIt looks like this
/*6*/ qs(small, (sortedSmall)=>{
/*7*/ qs(big, (sortedBig)=>{
/*8*/ next([...sortedSmall, pivot, ...sortedBig])
Copy the codeThe effect of this change is to write all subsequent operations as a function and pass it as an argument to the next quickSort!
Fang: yes!
Student: Exactly. You don’t have to go back when you pass something back. That’s brilliant! I have nothing to say… But there’s something weird about it.
This style of code is called CPS (continuation-passing style). We’ll talk about it later.
Student: So, can all recursions be rewritten as tail recursions?
Fang: Yes, you can watch the q&A on StackOverflow for detailed discussion, but don’t watch it, just remember the conclusion.
Student: Today’s class is making my brain explode. I need to take a break and play a video game.
Fang: Ok, but let’s finish by reviewing what we learned today:
- There is a special form of recursion called tail recursion
- Recursive versions of factorial can be written as “tail recursion” by passing the result of the previous call to the next one
- Recursive Fibonacci can be written as “tail recursion” by passing the results of the last two calls to the next call
- Recursive quicksort can be written as “tail recursion” by writing subsequent operations as a function that is passed on to the next call (CPS)
- One more thing to add: there are other ways to rewrite a recursion as a tail recursion, not just the one I talked about in class
Student: Is that all we’ve covered today? I feel like I’ve covered a lot of ground today…
Fang: That’s it. You didn’t miss it, did you? Take notes!
Student: Next time, I’ll play games first, bye!