Advertisement
Published in:
2021 | OriginalPaper | Chapter
11. More Fun with Recursion
Authors : Donald Sannella, Michael Fourman, Haoran Peng, Philip Wadler
Published in: Introduction to Computation
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
We’ll now look at more examples of recursively defined functions which demonstrate some points that didn’t arise in earlier examples. To start, recall the notation
[1..10]. Underlying this notation is the following Prelude function, where [m..n ] stands for enumFromTo m n: Here the recursion is on integers rather than lists. We’ve learned how important it is that recursion is well-founded: it’s okay to define the result of applying a function to a value in terms of its application to a smaller value. But here, we’re defining enumFromTo m n in terms of enumFromTo (m+1) n! Of course, m+1 is larger than m; how can that be right? And the first equation must be the base case, since there is no recursion, but it looks different from all of the previous examples, so what’s going on there?.