{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Lecture 3: Recursion\n", "\n", "Originally by Sriram Sankaranarayanan \n", "\n", "Modified by Ravi Mangal \n", "\n", "Last Modified: Jan 29, 2025." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In this lecture, our plan is to investigate the following concepts.\n", "\n", "- What is a recursive function?\n", "- Termination of recursive functions\n", "- Cost of recursive functions: Recursion depth and Number of recursive calls\n", "- Optimizing recursive functions via tail recursion\n", "- Mutually recursive functions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## What is a recursive function?\n", "\n", "A function $f$ is defined recursively if the body of the definition refers back to $f$. The easiest example is that of the `factorial` function, which we have already encountered before.\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36mfactorial\u001b[39m" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def factorial(x: Int): Int = {\n", " if (x == 0) {\n", " 1 // This is called the base case\n", " } else { \n", " x * factorial(x-1) // The recursion is here. \n", " }\n", "}" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mx1\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m120\u001b[39m\n", "\u001b[36mx2\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m3628800\u001b[39m" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val x1 = factorial(5)\n", "val x2 = factorial(10)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Factorial is recursive since in its body we are refering \n", "back to the function itself. This seems like a circular definition,\n", "and certainly prone to lots of abuse. For example, take a look at the `myCrazyMeaninglessVeryBadFunction` below. What is wrong with this function?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def myCrazyMeaninglessVeryBadFunction(x: Int): Int = {\n", " if (x == 0 ){\n", " 1 // The base case\n", " } else { \n", " x * myCrazyMeaninglessVeryBadFunction(x) // The recursion\n", " }\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The answer is simple: `factorial` _seems to_ terminate to provide an answer for all inputs, whereas `myCrazy...Function` simply does not terminate for any input. \n", "\n", "## Termination of recursive functions\n", "We will first consider simple recursive definitions that have the following form:\n", "\n", "$$ f(x) = \\left\\{ \\begin{array}{ll}\n", " \\text{constant} & \\text{if (base case condition holds)} \\\\\n", " \\text{.. expression involving f .. } & \\text{otherwise} \\\\\n", " \\end{array}\\right.$$\n", "\n", "Therefore, for any input $x_0$, we expect to observe a sequence of recursive calls: \n", "\n", "$$ f(x_0) \\rightsquigarrow f(x_1) \\rightsquigarrow \\cdots \\rightsquigarrow f(x_N) \\rightsquigarrow \\cdots $$\n", "\n", "We want that for every $x_0$ (starting value), the sequence obtained always reaches the base case condition and exits.\n", "\n", "__Definition (Termination)__ A recursive definition of a function $f(x)$ is terminating if and only if the sequence of recursive calls for any value of $x$ eventually hits the base case of the recursion.\n", "\n", "We already see that `myCrazy...Function` is not terminating and the reason is obvious: `myCrazy...Function(x)` calls back `myCrazy...Function(x)` thus going into an infinite loop.\n", "\n", "On the other hand, `factorial(x)` calls `factorial(x-1)`, which in turn calls `factorial(x-2)`, and so on. It is easy to see that for any $ x \\geq 0$, this process of unwinding the definitions will eventually get us to the base case `factorial(0)` and thus terminate. \n", "\n", "Therefore, is the factorial function terminating? Unfortunately, not as defined. This is where you have to be careful. It seems to terminate for inputs such as $2$.\n", "\n", "$$\\text{factorial(2)} \\rightsquigarrow \\text{factorial(1)} \\rightsquigarrow \\text{factorial(0)} \\,.$$\n", "\n", "But what about `factorial(-2)`? It exposes the issue.\n", "\n", "$$\\text{factorial(-2)} \\rightsquigarrow \\text{factorial(-3)} \\rightsquigarrow \\text{factorial(-4)} \\rightsquigarrow \\cdots \\,.$$\n", "\n", "The reader at this point may argue that `factorial(n)` was defined only for positive integers $n$. However, this is not reflected in the type of the Scala function: `factorial( x: Int): Int` which promises to return an integer whenever the input is an integer (that includes both positive and negative numbers).\n", "\n", "### Side Note: Preconditions\n", "\n", "A precondition is a constraint that restricts what inputs can be used to call a function. \n", "\n", "For instance, the `factorial` function has the precondition that its input must be non negative. In Scala we can use the `require` keyword to specify a precondition.\n" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36mfactorialWithPreconds\u001b[39m" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def factorialWithPreconds(x: Int): Int = {\n", " require(x >= 0)\n", " if (x == 0) {\n", " 1 // This is called the base case\n", " } else { \n", " x * factorialWithPreconds(x-1) // The recursion is here. \n", " }\n", "}" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36my\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m2\u001b[39m" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val y = factorialWithPreconds(2)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "ename": "java.lang.IllegalArgumentException", "evalue": "requirement failed", "output_type": "error", "traceback": [ "\u001b[31mjava.lang.IllegalArgumentException: requirement failed\u001b[39m", " scala.Predef$.require(\u001b[32mPredef.scala\u001b[39m:\u001b[32m324\u001b[39m)", " ammonite.$sess.cmd3$Helper.factorialWithPreconds(\u001b[32mcmd3.sc\u001b[39m:\u001b[32m2\u001b[39m)", " ammonite.$sess.cmd5$Helper.(\u001b[32mcmd5.sc\u001b[39m:\u001b[32m1\u001b[39m)", " ammonite.$sess.cmd5$.(\u001b[32mcmd5.sc\u001b[39m:\u001b[32m7\u001b[39m)" ] } ], "source": [ "val z = factorialWithPreconds(-2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Side Note: Preconditions versus Default Values\n", "\n", "Preconditions are very useful in software engineering practice. They expose the designer's expectations on what the inputs to a function should look like so that the execution can proceed without bugs. It is an important habit to try and write preconditions whenever appropriate.\n", "\n", "Another approach is to simply return a default value (say `-1` or `0`) when evaluating a function. The advantage is that it allows any input to execute without throwing an exception. However, the key disadvantage is that it imposes a requirement that the result of the function always be checked by the caller and the default values handled appropriately. Failing such a check often leads to _silent failures_ or failures that are see far away from the true cause. \n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Proving Termination\n", "\n", "The question of whether a recursive definition terminates is very important and at the same time a very hard problem. The main tool here is to show that the sequence of recursive calls from an input x _makes progress_ towards the base case condition. \n", "\n", "Consider the function `factorialWithPrecond(x: Int)` with input $x$ that satisfies the precondition $x \\geq 0$. \n", "\n", "- The base case of this call is $x = 0$.\n", "- Each call to `factorialWithPrecond(x)` with $x > 0$, results in the recursive call to `factorialWithPrecond(x - 1)`.\n", "\n", "Thus, we can combine the two statements to conclude that any call to `factorialWithPrecond(x)` will terminate in $(1 + x)$ steps provided $x \\geq 0$.\n", "\n", "Let us take another slightly more complex definition.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def fibonacci(n: Int): Int = {\n", " require ( n >= 0 )\n", " if (n <= 1) { 1 }\n", " else {\n", " fibonacci(n-1) + fibonacci(n-2)\n", " }\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`fibonacci` computes the $n^{th}$ Fibonacci number for $n \\geq 0$. We have added the precondition $n \\geq 0$ to enure that it is never callable on negative inputs and such. Is it terminating?\n", "\n", "A big difference between `factorial` and `fibonacci` is that while the former recursion involves just one call back to itself, `fibonacci` calls itself back twice. \n", "\n", "However, is it terminating?\n", "\n", "Yes it is and the same principles we used to understand factorial function can help us here. Each call to `fibonacci(n)` calls back `fibonacci(n-1)` and `fibonacci(n-2)`. The termination can be easily established through induction.\n", "- Base Case: `fibonacci(0)` terminates.\n", "- Induction Step: If `fibonacci(k)` terminates for all $ 0 \\leq k \\leq n-1$ and $n \\geq 1$, then so does `fibonacci(n)`.\n", " - Case 1: $ n = 1$. The base case applies and it terminates\n", " - Case 2: $ n \\geq 2$. \n", " - We can apply induction to see that both recursive calls `fibonacci(n-1)` and `fibonacci(n-2)` terminate. \n", " - To do so understand that the inductive hypothesis applies to $0 \\leq k \\leq n-1$. \n", " - We verify that $0 \\leq n-1 \\leq n-1$ and $0 \\leq n-2 \\leq n-1$.\n", "- Therefore, we can conclude that `fibonacci(n)` terminates.\n", "\n" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36misPowerOfTwo\u001b[39m\n", "defined \u001b[32mfunction\u001b[39m \u001b[36mrecurseToPowerOfTwo\u001b[39m" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "// Here are two recursions that look different.\n", "// Are they terminating?\n", "def isPowerOfTwo(x: Int): Boolean = {\n", " // Check if x is a power of two\n", " require( x >= 0)\n", " if (x == 0) { false }\n", " else if (x == 1) { true }\n", " else if (x % 2 == 1) { false }\n", " else {\n", " isPowerOfTwo(x / 2)\n", " }\n", "}\n", "\n", "def recurseToPowerOfTwo(x: Int): Int = {\n", " require( x >= 0)\n", " if (isPowerOfTwo(x)) { x }\n", " else {\n", " recurseToPowerOfTwo(x + 1)\n", " }\n", "}" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mz\u001b[39m: \u001b[32mBoolean\u001b[39m = \u001b[32mfalse\u001b[39m\n", "\u001b[36mw\u001b[39m: \u001b[32mBoolean\u001b[39m = \u001b[32mtrue\u001b[39m" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val z = isPowerOfTwo(15)\n", "val w = isPowerOfTwo(32)" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36me1\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m64\u001b[39m" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val e1 = recurseToPowerOfTwo(35)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36me2\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m256\u001b[39m" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val e2 = recurseToPowerOfTwo(135)" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36mM\u001b[39m" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "// Here is a famous recursion due to Manna, Pnueli and McCarthy. \n", "// Can you guess what it does?\n", "\n", "def M(x: Int): Int = {\n", " if (x > 100) { x - 10 }\n", " else { M(M( x+11 ))}\n", "}" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mx1\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m91\u001b[39m" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val x1 = M(-20)" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mx2\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m135\u001b[39m" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val x2 = M(145)" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mx3\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m91\u001b[39m" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val x3 = M(55)" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mx4\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m91\u001b[39m" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val x4 = M(12)" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mx5\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m91\u001b[39m" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val x5 = M(99)" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36mcollatz\u001b[39m" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "// Termination proof of this function is open.\n", "// See Collatz problem: which asks if this recursive\n", "// function below terminates on all inputs.\n", "\n", "def collatz(x: Int): Int = {\n", " require (x >= 0)\n", " if (x == 1) { 1 }\n", " else if (x % 2 == 1) { collatz (3 * x + 1 )}\n", " else { collatz (x / 2 )}\n", "}" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mv1\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m1\u001b[39m\n", "\u001b[36mv2\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m1\u001b[39m\n", "\u001b[36mv3\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m1\u001b[39m" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val v1 = collatz(51)\n", "val v2 = collatz(79)\n", "val v3 = collatz(352)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Cost of Recursive Functions: (Stack) Depth and Number of Calls" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You may be familiar from your computer systems classes as to how function calls are executed on a computer. \n", "- The system maintains a call stack with an `activation record` for each function call. \n", "- When a function is called, a new activation record is created for the called function that includes the return address (where in the program to return to when the call returns), the values of function call parameters and local variables to the function.\n", "- When a function returns, the control passes back to its caller at the return address stored in the stack.\n", "\n", "### Functions and Stack Management\n", "\n", "Consider the following code snippet:\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def f(x: Int): Int = {\n", " x * 5\n", "}\n", "\n", "def g(y: Int): Int = {\n", " val tmp = f(y)\n", " tmp * 10\n", "}\n", "\n", "def h(z: Int): Int = {\n", " val tmp2 = g(z)\n", " tmp2 + 5\n", "}\n", "\n", "h(15)\n", "// stuff that follows h(15)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The call to `h(15)` causes an activation record for `h` to be created. We will not really go into the details of how the Java Virtual Machine (JVM) does activation records.\n", "\n", "The activation record for the call to h looks somewhat like a table with the following information:\n", "\n", "~~~\n", "Activation record for h\n", "Return Address: Line 16.\n", "z: 15\n", "tmp2: ....\n", "~~~\n", "\n", "Now `h` executes with `z: 15` and it issues a call to `g` with `z` as the argument. \n", "Therefore, a new activation record is created and placed on top of the stack.\n", "\n", "~~~\n", "Activation record for g.\n", "Return Address: line 12.\n", "y: 15\n", "tmp: ...\n", "\n", "Activation record for h\n", "Return Address: Line 16.\n", "z: 15\n", "tmp2: ...\n", "~~~\n", "\n", "Finally, `f` is called and a new activation record for `f` is created and placed on top of the stack.\n", "\n", "~~~\n", "Activation record for f.\n", "Return Address: line 7\n", "x: 15\n", "\n", "Activation record for g.\n", "Return Address: line 12.\n", "y: 15\n", "tmp: ...\n", "\n", "Activation record for h\n", "return Address: Line 16.\n", "z: 15\n", "tmp2: ...\n", "~~~\n", "\n", "When `f` finished executing, it returns `75` that gets placed in the val `tmp` for `g`. The activation record for `f` is taken out of the stack and the modified record for `g` looks like this.\n", "\n", "~~~\n", "\n", "Activation record for g.\n", "Return Address: line 12.\n", "y: 15\n", "tmp: 75 \n", "\n", "Activation record for h\n", "return Address: Line 16.\n", "z: 15\n", "tmp2: ...\n", "~~~\n", "\n", "Similarly, `g` finishes its execution and returns 750 back to its caller.\n", "\n", "~~~\n", "Activation record for h\n", "return Address: Line 16.\n", "z: 15\n", "tmp2: 750\n", "~~~\n", "\n", "As you can see the stack grows with a function call when a new activation record is added and shrinks when a function returns.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "### Analyzing Cost of Recursive Functions via Recursion Tree\n", "\n", "Thus, recursive calls are implemented much like any other function call. However, because these functions call themselves, the stack grows as recursive calls are made. We are interested in two aspects of the resource consumption:\n", "\n", "- __Depth of Recursion:__ how many activation records can reside in the stack at any point during the execution of the recursive function, in the worst case?\n", "- __Number of Recursive Calls:__ How many calls are made to the recursive function in total?\n", "\n", "\n", "\n", "To facilitate this analysis, we can view the execution of a recursion as a tree wherein the root of the tree is the very first recursive call. For each node, the children are just the recursive calls made by that node. Leaves of the tree correspond to calls that fall into the base cases.\n", "\n", "\n", "\n", "The depth of the tree is therefore the depth of the recursion. The number of recursive calls is the number of nodes in the tree.\n", "\n", "\n", "#### Cost Analysis of Factorial Function\n", "\n", "Let us draw this tree for `factorial(5)`, having fixed the issue for factorial by adding `require(x >= 0)`.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def factorial(x : Int): Int = {\n", " require( x >= 0) // Fixed the issue!\n", " if (x == 0 ) 1 else {x * factorial(x-1)}\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here is the tree\n", "\n", "\n", "\n", "It is easy to see that the depth equals $6$ and the number of calls is also $6$.\n", "\n", "For general $n$, `factorial(n)` has stack depth $n+1$ and the number\n", "of calls is the same as the stack depth.\n", "\n", "#### Cost Analysis of Fibonacci Function\n", "\n", "Let us draw the tree for `fibonacci(4)`. \n", "\n", "\n", " \n", " \n", "The stack depth is 4, but the number of calls is 9.\n", " \n", "In general, the depth of `fibonacci(n)` is $n$. However, the number\n", "of calls is a different story.\n", "\n", "| n | Number of calls in `fibonacci(n)` |\n", "|---|-----------------------------------|\n", "| 0 | 1 | \n", "| 1 | 1 | \n", "| 2 | 3 | \n", "| 3 | 5 | \n", "| 4 | 9 | \n", "| 5 | 15 | \n", "\n", "What is the pattern here? Assuming $ n \\geq 2$, \n", "\n", "`# calls to fibonacci(n) = 1 + # calls to fibonacci(n-1) + # calls to fibonacci(n-2) `\n", " \n", "Thus, the recurrence for number of calls is given by\n", "\n", "$$C(n) = \\left\\{ \\begin{array}{rl}\n", "1 & n \\leq 1 \\\\\n", "1 + C(n-1) + C(n-2) & \\mbox{otherwise} \\\\\n", "\\end{array}\\right.$$\n", "\n", "These are called Leonardo numbers: https://oeis.org/A001595\n", "\n", "Unfortunately, the growth of the number of recursive calls is exponential in $n$. Thus, to compute `fibonacci(40)` requires us to make more than a billion calls. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Optimizing Recursive Functions \n", "\n", "### Tail Calls\n", "\n", "There is a very special case where the activation records do not have to grow upon successive function calls. These are called *tail calls*. Let us illustrate them with an example. \n", "\n", "**Example 1:** We already saw this example from above and traced out how the stack grows when the successive calls are made." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def f(x: Int): Int = {\n", " x * 5\n", "}\n", "\n", "def g(y: Int): Int = {\n", " val tmp = f(y)\n", " tmp * 10\n", "}\n", "\n", "def h(z: Int): Int = {\n", " val tmp2 = g(z)\n", " tmp2 + 5\n", "}\n", "\n", "h(15)\n", "// stuff that follows h(15)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Example 2:** Consider a different example below and carefully compare this code to that above." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def f1(x: Int): Int = {\n", " x * 8\n", "}\n", "\n", "def g1(y: Int): Int = {\n", " val tmp = 12 * y\n", " f1(tmp)\n", "}\n", "\n", "def h1(z: Int): Int = {\n", " val tmp2 = 14 + z\n", " g1(tmp2)\n", "}\n", "\n", "h1(15)\n", "// stuff that follows h(15)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Obviously, the functions are doing something totally different. But let us point out an important difference between the function call `g1(tmp2)` at line 12 of example 2 and the corresponding call `val tmp2 = g(z)` from line 11 of example 1. \n", "\n", "A key difference is that the result of the call `g1(tmp2)` in example 2 is returned back to the callee without any further computations whereas in example 1, the result is actually processed further by adding 5 and then returned.\n", "\n", "**Definition (Tail Call)** A function call `f(...)` is said to be a tail call if (a) no further computation is performed when the call to `f` returns back and (b) the result is passed back to the caller (without any modifications).\n", "\n", "For example all function calls in example 2 are tail calls whereas the calls in example 1 are not tail calls. \n", "\n", "Tail calls are important because they allow the system to perform an important optimization called *tail call optimization*.\n", "\n", "### Tail Call Optimization\n", "\n", "Let us see how this works with example 2. Consider the activation stack when `g1` is called inside function `h1`.\n", "\n", "~~~\n", "Activation Record for h1\n", "Return Address: line 16\n", "z: 15\n", "tmp2: 29\n", "~~~\n", "\n", "Normally, we will now call `g1(29)` and therefore a new activation record is added.\n", "\n", "~~~\n", "Activation Record for g1\n", "Return Address: line 13\n", "y: 29\n", "tmp: ... \n", "\n", "Activation Record for h1\n", "Return Address: line 16\n", "z: 15\n", "tmp2: 29\n", "~~~\n", "\n", "The key question is whether we need this? What happens when `g1` returns? Because it was called as a tail call, the value returned back to `h1` is just sent back to the caller.\n", "Tail call optimization is a very simple trick. Rather than keep the activation record for `h1` around, it simply **replaces** the activation record for `h1` as follows:\n", "\n", "\n", "~~~\n", "Activation Record for g1 (TAIL CALL OPTIMIZED)\n", "Return Address: line 16\n", "y: 29\n", "tmp: ... \n", "~~~\n", "\n", "There is a very key change in terms of the return address. Rather than return back from `g1` to `h1` and from `h1` to its caller, we will bypass the *middle man* and directly send our result to whosoever was waiting for `h1`.\n", "\n", "As a result of tail call optimization, we conclude that **tail calls need not cause the stack size to increase**." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Tail Recursion\n", "\n", "We will now look closer into tail recursion, which we briefly introduced earlier. Let us look at two examples of recursions." ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36mrecursionA\u001b[39m\n", "defined \u001b[32mfunction\u001b[39m \u001b[36mrecursionB\u001b[39m" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def recursionA(n: Int): Int = {\n", " if (n <= 0) { 1 }\n", " else {\n", " 10 * recursionA(n-1)\n", " }\n", "}\n", "\n", "\n", "def recursionB(n: Int, m: Int): Int = {\n", " if (n <= 0) { m }\n", " else {\n", " recursionB(n-1, 10 * m)\n", " }\n", "}\n" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mres19\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m100000\u001b[39m" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "recursionA(5)" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mres20\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m100000\u001b[39m" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "recursionB(5,1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us closely describe how both functions work. Both functions will return if the argument $n \\leq 0$. However, if $n > 0$, \n", "`recursionA` does the following:\n", "- call `recursionA` on $n-1$. \n", "- Multiply the return value by 10 and return the result.\n", "\n", "`recursionB` does the following:\n", "- Call the `recursionB` on $n-1$ and $10m$.\n", "- Pass the return value along _as is_.\n", "\n", "The important difference we highlight here is that `recursionA` performs further calculations on the result of the recursive call whereas `recursionB` does not:\n", "\n", "~~~\n", "recursionA: wait for recursive call to return. Multiply result by 10 and return it back.\n", "\n", "recursionB: wait for recursive call to return and simply return the result back to the caller.\n", "~~~\n", "\n", "Therefore, we say `recursionB` is tail recursive since it simply passes along the return value from the recursive calls as is.\n", "\n", "However, `recursionA` is not tail recursive since it performs further computing on the return value.\n", "\n", "- The `factorial` function is _not_ tail recursive as is. Why?\n", "- Is the `fibonacci` function tail recursive?\n", "- Is the function `isPowerOfTwo` tail recursive?\n", "- Is the function `M` tail recursive?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The important reason why we care about tail recursion is that since it simply passes along the return value as is, there is no need to keep its activation record. Simply, when we make the recursive call, we give this call the current return address so that it can directly pass its result along to the root call. \n", "\n", "\n", " \n", "The main takeaway is that tail recursive calls can effectively be turned into a while loop by the compiler, and the stack depth compressed to $1$.\n", "\n", "We can convert non-tail recursive recurrences to tail recursive ones.\n", "Here is how we do it for factorial. Note that we added an accumulator\n", "argument `acc` that carries around the product so far." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def tailRecursiveFactorial(n: Int, acc: Int): Int = {\n", " if (n == 0) { acc }\n", " else { tailRecursiveFactorial(n-1, acc * n) }\n", "}\n", "\n", "def factorial(n: Int): Int = tailRecursiveFactorial(n, 1)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "// Equivalent loop to tail recursive version\n", "def factorialLoop(n: Int): Int = {\n", " var j = n\n", " var acc = 1\n", " while (j >= 0){\n", " acc = acc * j\n", " j = j - 1\n", " }\n", " return acc\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Converting something more complicated like fibonacci to an _equivalent_ tail recursive version is more complicated. We can achive this by using two accumulators and thus effectively translating a while loop version into a tail recursive call." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "// j counts up from 1 to n\n", "// acc1 is fibonacci(j)\n", "// acc2 is fibonacci(j-1)\n", "// implement the while loop\n", "// while (j < n) { (acc1, acc2) = (acc1+ acc2, acc1)}\n", "// return acc1\n", "\n", "def fibonacci(n: Int, j: Int = 1, acc1: BigInt = 1, acc2: BigInt = 1): BigInt = {\n", " if (n == 0 ) { BigInt(1) }\n", " else if (j == n) { acc1 }\n", " else {\n", " fibonacci(n, j+1, acc1 + acc2, acc1)\n", " }\n", "}" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "val v1 = fibonacci(5)\n", "val v2 = fibonacci(7)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Mutually Recursive Functions\n", "\n", "Just like we have functions that call themselves, it is possible to have mutually recursive functions that are defined in terms of each other. \n", "In the example below, m1 calls m2 and m2 calls m1. This is an example of a mutual recursive function. Is it tail recursive? " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def m1 (x: Int): Int = {\n", " if (x <= 2) { x } \n", " else {\n", " (m2( (x/2+1).toString )).toInt\n", " } \n", "}\n", "\n", "def m2(s: String): String = {\n", " if (s.length() <= 1) { s }\n", " else {\n", " val t = s.substring(0, s.length() -1 )\n", " m1(t.toInt).toString\n", " }\n", "}\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "val s1 = m1(250)\n", "val s2 = m1(90)\n", "val s3 = m1(1001)\n", "val s4 = m1(30091)" ] } ], "metadata": { "kernelspec": { "display_name": "Scala", "language": "scala", "name": "scala" }, "language_info": { "codemirror_mode": "text/x-scala", "file_extension": ".sc", "mimetype": "text/x-scala", "name": "scala", "nbconvert_exporter": "script", "version": "2.13.14" } }, "nbformat": 4, "nbformat_minor": 4 }