Recursion in Purescript

Vincent Orr
InstructorVincent Orr

Share this video with your friends

Send Tweet
Published 4 years ago
Updated 3 years ago

In PureScript, you pattern match against the base case to achieve recursion.

In this lesson, you will learn exactly how to do that by implementing a recursive solution to a factorial function.

Instructor: [00:00] to do this, we'll create a function called fact. That will take an int and return it an int. Pattern match on that, and what we'll do is fact 0that returns us 1. Then, fact n, that will return us n*fact and n-1.

[00:14] It might have become apparent that we're actually creating a factorial function. We'll test this out, and it's fact 3, that will return us 6. Let's try fact 6, and that will return us 720. Let's quickly explain how a factorial works. Passing 6 to our factorial function would actually be 65432*1. That would return us 720.

[00:42] When you first call factorial, the n becomes a 6, and a 6 here. Then, you're doing 6-1, which is 5. We're using the 5 to actually pass back into fact, which would then do fact 5 * fact 4 * fact 3 * 2 * 1. Technically once it had reached 1, what it'd do would be fact 1-1, which would give us fact 0That would return a 1.

[01:09] Pattern matching against 0is what we do to get out of our function. If you imagine that we didn't, then it'd keep going into -1, -2, -3, and so on, right up to the point where you'd end up having a slack overflow and everything blowing up.

[01:22] Now, you should be able to see how we're creating this recursion by calling fact within fact and continuing to the point where we pattern match against 0That would come out of our recursion and return us the result which is 720. There you have it, how to do recursion in PureScript.