{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Thinking Recursively in MeTTa\$n", "\n", "MeTTa is a great programming language for learning to think recursively. When you first encounter recursion, it can feel a lot like magic. This can be a good thing or a bad thing, depending on your point of view. If you're the kind of person who loves watching magic shows, who loves the feeling of being \"taken in\" by the illusion, you'll probably immediately enjoy writing recursive programs. On the other hand, if you're the kind of person who wants to know what's really going on behind the scenes (\"how did they _do that_?!\"), who feels a nagging sense of unease after seeing a really convincing magic trick unfold before your eyes because you can't figure out how it was done...well, you may initially find recursion to be a bit perplexing and frustrating. But fear not! I, too, was in the latter category when I first encountered recursion, way back when. But recursion has a way of growing on you over time, and I predict that with a little perseverance, you too will soon come to appreciate its many magical charms.\n", "\n", "One of the paradoxical qualities that often makes learning to write recursive programs so hard is that writing recursive programs is so _easy_ (once you get the hang of it). But getting the hang of it usually takes a lot of practice, because you really do have to learn to _think_ in a new and unfamiliar way. The good news is that if you keep the following rules of thumb in mind whenever you are faced with the task of writing a recursive program, it will make the task much easier. So here we go..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### The Base Case\$n", "\n", "The first thing you always have to do when writing a recursive program is to ask yourself: what is the _base case_ for this program? The \"base case\" is the simplest form of input data that your program will ever have to deal with, and the details of what that means will depend on exactly what your program is supposed to do. Sometimes a program may even have multiple base cases.\n", "\n", "Suppose we wish to write a MeTTa function called addup that takes in a list of numbers and adds them all up. The list might contain anywhere from a single number to a million numbers or more, or possibly no numbers at all. For addup, the \"simplest form of input data\" would just be the empty list. No thinking at all is required to figure out the sum of an empty list, because the answer is obviously 0. So here is a preliminary sketch of our function definition for addup:\n", "\n", "```scheme\$n", "(= (addup\$n", " $nums)\n", " (case\$n", " ((null? $nums) 0)\n", " ...\n", "```\n", "\n", "Notice how we use (null? $nums) to check for the empty list. This is the appropriate base-case condition for addup. In general, however, the correct base-case condition for a function will depend on the type of data that the function expects, as well as what it is supposed to compute. For other recursive functions that take a list as input, it might be more appropriate to check if the list has exactly one element, rather than no elements. For functions that operate on numbers, the base case might be when the input is equal to zero." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### The General Case\$n", "\n", "Our function definition is still incomplete, but it should be clear that the code sketched above will give the right answer for our base case. So far so good. Next, we need to consider how our function should handle the _general case_ — that is, input data other than the base case. For addup, that means any list containing at least one number. For example, the list (1 2 3 4 5 6). Or maybe a list containing a million numbers.\n", "\n", "Now we come to the magic. Even though we're not yet finished with our function definition, we're going to make a crazy assumption. We're going to simply pretend that addup somehow _already works correctly_ on _any_ list that we give it, and we're going to _use that assumption_ to help us complete the function definition. For example, suppose we call addup on the input list (1 2 3 4 5 6). This list is not empty, so the base-case clause of the cond gets skipped. How then do we figure out the sum of all the numbers? Answer: we will use addup itself to help us out! We first make our list slightly shorter by calling (cdr $nums), which gives us the list (2 3 4 5 6). Then we call addup recursively on that shorter list, which we just _assume_ will somehow magically give us 20, since 20 is the sum of the shorter list (2 3 4 5 6). But we're not quite finished yet, because we still need to add the first number in the original list, namely the 1 (which we temporarily dropped before calling the recursion), to this sum to get the correct answer for the _whole_ list. Here is the complete recursive definition:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "(= (addup\$n", " $nums)\n", " (case\$n", " ((null? $nums) 0)\n", " (%void% (+ (car $nums) (addup (cdr $nums)))))))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Will this really work? Let's try it out!" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "(addup (1 2 3 4 5 6))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "(addup (10 6 3 9 18 5 2 2 7 15 4 6 9 8 24 42 77 0 1 32))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In the first example, $nums is the list (1 2 3 4 5 6), (car $nums) is 1, (cdr $nums) is the list (2 3 4 5 6), and (addup (cdr $nums)) is 20. In the second example, (car $nums) is 10, and (addup (cdr $nums)) gives 270, which is the sum of all of the remaining numbers in the list. This then gets added to the 10 to give the final answer of 280 for the entire list.\n", "\n", "How can we be sure that (addup (cdr $nums)) really will give us the correct answer for the shorter list in all cases? After all, we just magically _assumed_ that it will. The beauty of recursion rests on the principle of _mathematical induction_, which guarantees that your program will work correctly in all cases as long as the following three things are true:\n", "\n", "1. Your program gives the correct answer for the base case.\n", "\n", "2. Your program only calls itself recursively on _simpler_ versions of the input data.\n", "\n", "3. Your program uses the answer given by the recursion to construct an appropriate answer for the original input data.\n", "\n", "In our example, addup calls itself recursively on (cdr $nums), which is \"simpler\" than $nums because it is shorter by one number. Even if $nums contains a million numbers, (cdr $nums) will be slightly shorter, and thus slightly \"closer\" to the base case. Furthermore, addup adds the first number in the list to the sum computed by the recursion, in order to form the correct answer for the whole list. This is typical of recursive functions: after calling themselves recursively, they usually need to do a little more \"work\" before returning their final answer. But the bulk of the work — such as figuring out the sum of the cdr of the list, even if the cdr contains thousands or millions of numbers — is handled \"magically\" by the recursive call." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Another Example\$n", "\n", "Let's try a slightly more sophisticated example. This time we will write a function called smallest that takes in a list of numbers and returns the smallest one, instead of adding them all up. The list might contain anywhere from a single number to a million numbers or more. For this example, let's stipulate that the list will never be empty, because asking for the smallest number of an empty list doesn't make any sense. Here the \"simplest form of input data\" would be a list containing just a single number, such as (42). No thinking at all is required to figure out which of the numbers in the list is the smallest, because there's only one number. So we can just return that number, whatever it is, and we're done. Note that we need to return the number itself, not the list, as our answer, because the job of smallest is to return the smallest _number_ from the list. In other words, we need to use the car operation to retrieve the number from the list. But that's easy enough to do. So here is a preliminary sketch of our function definition for smallest:\n", "\n", "```scheme\$n", "(= (smallest\$n", " $nums)\n", " (case\$n", " ((null? (cdr $nums)) (car $nums))\n", " ...\n", "```\n", "\n", "Notice how we use (null? (cdr $nums)) to check if the list contains exactly one number. This is the appropriate base-case condition for smallest. Although our function definition is still incomplete, it should be clear that the code sketched above will give the right answer for each of the following input lists (and indeed, for any list containing a single number):\n", "\n", "```scheme\$n", "(smallest (42)) => 42\$n", "(smallest (-5)) => -5\$n", "(smallest (1000)) => 1000\$n", "```\n", "\n", "So far so good. Now, what about the general case? For smallest, that means any list containing more than one number. For example, the list (9 5 10 3 18). Or maybe a list containing a million numbers, with the smallest number buried somewhere far down in the middle or toward the end of the list.\n", "\n", "Once again, it's time for some magic. Even though we're not yet finished with our function definition, let's pretend that smallest somehow _already works correctly_ on _any_ list that we give it, and let's _use that assumption_ to help us complete the function definition. For example, suppose we call smallest on the input list (9 5 10 3 18). This list contains more than one number (that is, its cdr is not null), so the base-case clause of the cond is skipped. How then do we retrieve the smallest number from the list? Answer: just like before, we will use the function _recursively_ to help us out! We first make our list slightly shorter by calling (cdr $nums), which gives us (5 10 3 18). Then we call smallest recursively on that shorter list, which we just _assume_ will somehow magically give us 3, since 3 is the smallest number in the shorter list (5 10 3 18). But we're not quite finished yet, because we still need to compare the 3 to the first number in the original list, namely the 9 (which we temporarily dropped before calling the recursion), to make sure that the 3 really is the smallest number in the _whole_ list. In this case, the 3 is in fact smaller than the 9, so we return the 3 as our final answer, and we're done. On the other hand, if the original list had been (2 5 10 3 18), the first number (the 2) would be _smaller_ than the 3, and so we would need to return the 2 instead of the 3. Here is the complete recursive definition:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "(= (smallest $nums)\n", " (case\$n", " ((null? (cdr $nums)) (car $nums))\n", " ((< (car $nums) (smallest (cdr $nums))) (car $nums))\n", " (%void% (smallest (cdr $nums))))))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Will this really work? Let's try it out!" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "(smallest (9 5 10 3 18))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "(smallest (2 5 10 3 18))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "(smallest (7 4 2 13 9 1 8 9 15 3))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To summarize: in the first example, $nums is the list (9 5 10 3 18), (cdr $nums) is the list (5 10 3 18), (car $nums) is 9, and the recursive call (smallest (cdr $nums)) gives 3, so 3 gets returned as the final answer because 3 is smaller than 9. The second example is similar, except that (car $nums) is now 2, which is smaller than 3, so the 2 gets returned instead of the 3. In the third example, (smallest (cdr $nums)) gives 1, which is smaller than the 7 at the front of the list, so the 1 is returned instead of the 7.\n", "\n", "Just like addup, smallest calls itself recursively on (cdr $nums), which is \"simpler\" than $nums because it is shorter by one number, and thus slightly \"closer\" to the base case. This recursive call performs the bulk of the work: namely, figuring out the smallest number in the cdr of the list. Even if the cdr contains thousands or millions of numbers, the recursive call will \"magically\" give the right answer for the cdr. Unlike addup, however, the \"additional work\" done by smallest is to _compare_ the number returned by the recursion to the first number in the list, instead of adding them together, in order to determine the correct answer for the whole list. It doesn't just blindly return (smallest (cdr $nums)) in every case, because that won't be the correct answer if (car $nums) happens to be the smallest number in the whole list. An additional decision is necessary to ensure that smallest works for every list.\n", "\n", "### An Important Caveat\$n", "\n", "The above examples illustrate the right way to approach thinking about recursion. Understanding how a recursive function works is easiest if you think about it _on just the top level_. In other words, like we did above, just assume that the recursion will magically give you the right answer, and don't worry about what actually happens \"inside\" the recursive call — provided that you always call it on \"simpler\" versions of the input data. If your function explicitly handles the base case correctly, and uses the results of the recursive call in the right way to construct an appropriate answer for the original input data, mathematical induction will see to it that your function works correctly in all cases.\n", "\n", "That said, even perfectly correct recursive code can sometimes lead to severe inefficiencies in execution speed. For example, if you played around with smallest, you may have noticed a dramatic slowdown in speed on lists that are only slightly longer than the examples given above. The reason for this is not hard to see. Suppose we call smallest on the list (14 13 12 11 10 9 8 7 6 5 4 3 2 1). The recursive call (smallest (cdr $nums)) gives 1. This result is compared to (car $nums), which is not less than 1, so the else line of the conditional gets executed next. This generates a second — identical — recursive call to (smallest (cdr $nums)), which just re-computes the 1 all over again. This redundant computation happens on every level of the recursion, all the way down to the base case, leading to an exponential slowdown in speed.\n", "\n", "Fortunately, this problem is very easy to fix, but requires rewriting the code in a slightly different way using a feature of MeTTa that I will introduce a little later on in the semester. For now, the important thing is to learn to think recursively. We won't worry too much about efficiency at this point, because it is often easy to transform a correct but inefficient program into a much more efficient one by applying some simple optimizations." ] } ], "metadata": { "kernelspec": { "display_name": "Vspace MeTTa 3", "language": "scheme", "name": "vspace_scheme" }, "language_info": { "codemirror_mode": { "name": "scheme" }, "mimetype": "text/x-scheme", "name": "scheme", "pygments_lexer": "scheme" }, "widgets": { "application/vnd.jupyter.widget-state+json": { "state": {}, "version_major": 2, "version_minor": 0 } } }, "nbformat": 4, "nbformat_minor": 4 }