{"assignment":{"_schema_version":2,"course_id":37,"date_created":"2022-06-28T19:00:00+00:00","date_modified":"2023-09-10T14:22:12.040307+00:00","extra_instructor_files":"","extra_starting_files":"","forked_id":null,"forked_version":null,"hidden":false,"id":1123,"instructions":"## Defining Recursion\n\n- **Recursion:** A process in which the result of each repetition is dependent upon the result of the next repetition.\n- If you still don't understand, go see the definition of recursion.\n\nRecursion is another approach to looping, where each repetition is dependent upon the result of the next repetition.\nBy solving the next version of a problem, which will be smaller than the current problem, you can solve the current problem.\nThe trick is that at some point, you must solve a version of the problem that is so small that the problem is trivial.\nAt that point, you stop the repetition and \"unwind\" the result back.\n\n## Recursion in Code\n\n```python try-recursion\ndef add_numbers(current_number: int) -> int:\n    # Branch\n    if current_number <= 0:\n        # Base case\n        return 0\n    # Recursive case\n    next_value = add_numbers(current_number-1)\n    # Combine\n    return current_number + next_value\n\nprint(add_numbers(10))\n```\n\nRecursion is a powerful idiom in code for solving certain kinds of problems.\nThe key part of recursive code is a function that calls itself in its own definition.\nThe following `add_numbers` function calls itself on the sixth line of its own body.\nThis may seem impossible since it would imply that the function will just keep calling itself repeatedly or that the function would execute before it's finished being defined.\nYou must understand two things.\nFirst, successful recursion _always requires_ an `if` statement or other kind of loop to terminate correctly.\nSecond, function definitions happen _before_ function calls, and the body of the function is NOT executed during the definition.\nIf things still seem murky, don't worry, because we're going to look at recursion quite a few ways before we're done.\n\n## Recursive Art\n\n![A painting of two hands drawing a smaller painting of two hands drawing an even smaller painting of two hands, and so on.](bakery_advanced_recursion_hands.png)\n\nRecursion sometimes demonstrated in art, as represented in the drawing on the left of a pair of hands drawing another picture of the same scene.\nIn the smaller picture being drawn are a smaller pair of the same hands drawing a smaller version of the same picture.\nThat smaller picture contains yet another pair of smaller hands drawing an even smaller version of the picture, and so on and so on.\nAdditionally, we see the painting on the right: an artist draws a painting, and then another artist draws a painting of the original artist holding their painting.\nThen, another artist draws a painting of the second artist holding the original artist's painting.\nThe images get smaller and smaller but eventually terminate at some finite size.\nAt least, as far as we can see.\n\n## Recursive Work\n\n![An organizational chart showing a recursive hierarchy](bakery_advanced_recursion_org_chart.png)\n\nNow let us consider an alternative scenario where we are hiring someone to complete a job.\nWe hire Alejandra, who in turn hires two subcontractors Bob and Carol to do the work.\nBob then hires two sub-subcontractors, Danielle and Edward.\nMeanwhile, Carol hires two sub-subcontractors of her own, Gregory and Felienne.\nEventually, we reach a level where folks get the job done.\nWhen they finish, they report back to their bosses, who in turn report back to Alejandra.\nBy carefully breaking down the work, each individual job is quite small although we have a lot of employees.\n\n## Tree Vocabulary\n\n![A diagram visually depicting the terms node, edge, parent, child, root, and leaf.](bakery_advanced_recursion_vocabulary.png)\n\nIn coding, this type of structure is called a _tree_, where the structure repeats itself as you go downwards.\nTrees are composed of individual _nodes_, and each node has zero or more edges below it.\nThese edges connect _parent nodes_ to their _child nodes_.\nThe nodes at the bottom of the tree without any children of their own are called _leaf nodes_.\nThe node at the very top is called the _root node_.\n\n## Trees in Python\n\n```python\nfrom dataclasses import dataclass\n\n@dataclass\nclass Tree:\n    pass\n\nEMPTY = Tree()\n\n@dataclass\nclass BinaryTree(Tree):   # <-- Note (Tree) part!\n    value: int\n    left: Tree\n    right: Tree\n```\n\nThere are many ways to represent trees in Python, but we will start with one that uses dataclasses.\nFirst, we define a dataclass without any fields named `Tree`.\nThat dataclass is used to create a special `Tree` instance stored in a constant named `EMPTY`, which will represent an empty tree with no children.\nNotice that we call the constructor without any arguments since there is no data stored in the empty basic `Tree`.\n\nThen comes the more important and interesting definition for a `BinaryTree`.\nThe word _binary_ here refers to how all our trees will have exactly two children, represented by the `left` and `right` fields of the `BinaryTree` dataclass.\nThe third field is the actual data for an individual node in the tree, which we will call `value`.\nFinally, we want to draw your particular attention to the parenthetical `Tree` in the header of the `BinaryTree` class definition.\nThis extra code is critical to making the structure work via _inheritance_.\n\n## Non-recursive Inheritance\n\n```python\nfrom dataclasses import dataclass\n\n@dataclass\nclass Media:\n    name: str\n\n@dataclass\nclass Movie(Media):\n    duration: int\n    frames_per_second: float\n\n@dataclass\nclass Book(Media):\n    pages: int\n    hardcover: bool\n\nprint(Book(\"Wizard of Oz\", 272, True))\nprint(Movie(\"Wizard of Oz\", 112, 30.0))\n```\n\nInheritance has nothing to do with recursion.\nInheritance is a powerful feature of classes that allows us to reuse fields and functionality between related dataclasses.\nThis is also useful for describing related types of objects.\nIn this example, since we put `Media` inside parentheses in the headers of both `Movie` and `Book`, we have established an inheritance relationship.\nThat means that all books are media, and all movies are also media.\nAt the same time, books are not movies, and movies are not books.\nBut since these two classes share the `name` field in common, we have that field in the `Media` class, making it available in both of the classes indirectly.\nWe could now define functions that consume lists of `Media` and use their `name` field, which means that we could have a list that contains both books and movies.\nEven though we previously said that lists could not contain more than one type, those two types are unified by the `Media` type via inheritance.\nThis will be critical in letting us create functions that consume `Tree`s, which can be `BinaryTree`s with two children and `EMPTY` trees with zero children.\n\n## Instances of Trees\n\n```python try-inheritance\nfrom dataclasses import dataclass\n\n@dataclass\nclass Tree:\n    pass\n\n@dataclass\nclass BinaryTree(Tree):\n    value: int\n    left: Tree\n    right: Tree\nEMPTY = Tree()\n\none_tree = BinaryTree(9, EMPTY, EMPTY)\nthree_tree = BinaryTree(4, BinaryTree(5, EMPTY, EMPTY),\n                           BinaryTree(7, EMPTY, EMPTY))\nprint(EMPTY)\nprint(one_tree)\nprint(three_tree)\n```\n\nComing back to our definition of a `Tree`, it may help to look at an example.\nIn the code shown here, we end up creating three variables to hold `Tree` instances.\nThe first is the `EMPTY` variable which we will always create and which holds an empty, boring `Tree` instance with nothing inside.\nThe next variable is a more interesting example named `one_tree`, which holds an instance of the `BinaryTree` dataclass.\nRecall that the `BinaryTree` class inherits from `Tree`, which means that `one_tree` is also a `Tree`, just like `EMPTY`.\nTo create an instance of a `BinaryTree`, we need a value and two other `Tree` instances.\nWe store the value `9` in this tree (which becomes the root value), and then use the `EMPTY` instance for the `left` and `right` children.\nThis represents a binary tree with only one node, which is simultaneously the root and the leaf.\nThe last variable, `three_tree`, is even more interesting, since it represents a binary tree with three nodes.\nThe root node holds the value `4` and has two children.\nThe `left` child's value is `5` and the `right` child's value is `7`.\nAll the children's children are `EMPTY` trees.\n\n## Longer Example\n\n```python organization-example\n# Example definition of a Tree of strings\nfrom dataclasses import dataclass\n\n@dataclass\nclass Tree:\n    pass\n\n@dataclass\nclass BinaryTree(Tree):\n    name: str\n    left: Tree\n    right: Tree\n\nEMPTY = Tree()\n\norganization = BinaryTree(\"Alejandra\",\n    BinaryTree(\"Bob\", BinaryTree(\"Danielle\", EMPTY, EMPTY),\n                      BinaryTree(\"Edward\", EMPTY, EMPTY)),\n    BinaryTree(\"Carol\", BinaryTree(\"Gregory\", EMPTY, EMPTY),\n                        BinaryTree(\"Felienne\", EMPTY, EMPTY)))\nprint(organization)\n```\n\nNow let's return to the employee and subcontractor example from before.\nThis time, we modified our `BinaryTree` definition slightly, replacing the `value` integer field with a `name` string field.\nThe `organization` variable holds a `BinaryTree` with the `name` \"Alejandra\", which has two children.\nThe first child has the value \"Bob\" and two more `BinaryTree` in its children, with the values \"Danielle\" and \"Edward.\" Going back up a level, the second child of Alejandra was \"Carol,\" with her two children \"Gregory\" and \"Felienne.\" Although the structure may be a little hard to read, this is all one giant binary tree with seven nodes.\nNow, you may be wondering why we use the `EMPTY` tree as children of the leaf nodes.\nFirst, you must remember that we must pass a `Tree` in for the `left` and `right` when making new `BinaryTree` instances.\nThat means we must use either a `BinaryTree` (which would have two of its own children) or the empty `Tree` instance (which has no children.) We'll see how this makes our lives easier when we start writing functions that operate on trees.\n\n## Recursive Functions\n\n```python count-people\nfrom dataclasses import dataclass\n\n@dataclass\nclass Tree:\n    pass\n\n@dataclass\nclass BinaryTree(Tree):\n    name: str\n    left: Tree\n    right: Tree\n\nEMPTY = Tree()\n\ndef count_people(tree: Tree) -> int:\n    if tree == EMPTY:\n        return 0\n    left_value = count_people(tree.left)\n    right_value = count_people(tree.right)\n    return 1 + left_value + right_value\n\nprint(count_people(BinaryTree(\"Alejandra\", EMPTY, EMPTY)))\n```\n\nHere is an example recursive function that consumes a `Tree` containing people.\nIn the very first line of the function, we begin by checking if the `tree` parameter is the `EMPTY` tree.\nIf we are ever given the `EMPTY` tree, we return `0` since there are no people in an empty tree.\nOtherwise, we proceed onward with the body of the function.\nIf we are not in the empty tree; that means we are currently looking at a tree with at least one person and possibly two children in the `left` and `right`.\nTo determine the number of people in those two branches of the tree, we can reuse the `count_people` function that we are currently defining.\nWe count the number of people on the left and store the result in a variable, then we do the same for the right.\nAfter both sides have been counted, we combine those results with `1`, representing the person in this node of the tree, and return the result.\n\n## Template\n\n```python\ndef function_name(tree: Tree) -> ___:\n    # Branch\n    if tree == EMPTY:\n        # Base case\n        return ___\n    # Recursive case: recursive calls with simplification\n    left_side = function_name(tree.left)\n    right_side = function_name(tree.right)\n    # Combination\n    return tree.___ ??? left_side ??? right_side\n```\n\nGenerally, the format of a recursive function always has four parts.\nFirst, there must be a _conditional branch_ using an `if` statement at the beginning, to determine if we are dealing with the `EMPTY` tree or a `BinaryTree`.\nIf the `tree` is `EMPTY`, then we are in the _base case_ and can immediately `return` whatever basic value makes sense for this case, usually zero or the empty string.\nHowever, if the tree we are given is not `EMPTY`, then it must be a `BinaryTree`, which means we will need to check its fields.\nWe call this the _recursive case_ and this is usually where people tend to get confused.\n\nTwo things must happen inside the recursive case: a _recursive call with simplification_ and the _combination of the results_.\nThe \"recursive call\" is when the function we are defining is called right in its own body.\nThe \"simplification\" refers to how the arguments to that recursive call should be a simpler version of the original parameter.\nIn our code, that means we use `tree.left` and `tree.right`, as opposed to using `tree`, since those will eventually be the simplest value possible, our `EMPTY` tree.\nFrom a type perspective, this is perfectly valid: those two fields are both `Tree`s, and we know our recursive function takes in a `Tree`.\nAre they `EMPTY` trees or `BinaryTree` objects? We do not know, and we don't even care.\nThe recursive function that we call will handle them either way and return the appropriate result.\nWe just have to trust that it will work out and continue defining the rest of our function.\n\nWhen the recursive function calls are done, we store their result in two variables: `left_side` and `right_side`.\nWe combine these two variables along with the actual value field from the current `tree` instance.\nThe underscore indicates how this attribute may vary from problem to problem, and the question marks indicate how the combination operator may not always be addition.\nThe result of the combination is returned, finishing the recursion.\nLet us examine at least one more example.\n\n## Another Example Function\n\n```python render-people\nfrom dataclasses import dataclass\n\n@dataclass\nclass Tree:\n    pass\n\n@dataclass\nclass BinaryTree(Tree):\n    name: str\n    left: Tree\n    right: Tree\n\nEMPTY = Tree()\n\ndef render_people(tree: Tree) -> str:\n    if tree == EMPTY:\n        return \"\"\n    left_value = render_people(tree.left)\n    right_value = render_people(tree.right)\n    return tree.name + \", \" + left_value + right_value\n\nprint(render_people(BinaryTree(\"Alejandra\",\n    BinaryTree(\"Bob\", BinaryTree(\"Danielle\", EMPTY, EMPTY),\n                      BinaryTree(\"Edward\", EMPTY, EMPTY)),\n    BinaryTree(\"Carol\", BinaryTree(\"Gregory\", EMPTY, EMPTY),\n                        BinaryTree(\"Felienne\", EMPTY, EMPTY)))))\n```\n\nThis longer example finally demonstrates running a recursive function on the entire organization that we defined before.\nNotice the changes to our recursive function.\nFirst, we are now returning a string value in the case of an `EMPTY` tree, specifically the empty string.\nSecond, in the combination step, we are using the `tree.name` along with a comma.\nSince this function gets called on each `BinaryTree`, every person ends up having their name followed by a comma.\nTracing through this code in a debugger will help you understand the precise and delicate set of calls occurring.\n\n## Summary\n\n- Recursion is when something is made up of parts that resemble the whole thing:\n  - Recursive data structures are when a bigger structure is made up of smaller structures of the same type.\n  - Recursive functions are when the function's definition calls the function being defined.\n- To eventually terminate, a recursive function must have a:\n  - Conditional branch: A conditional that checks if this function call should follow the base case or the recursive case.\n  - Base case: Determines whether the function has reached the end of the data and should return some kind of basic value.\n  - Recursive case with simplification: Call the function being defined, but the argument must be \"simpler\" (smaller) than the original argument passed in so that the new function invocation will eventually reach the base case.\n  - Combination: The results of the recursive call(s) should be combined with the current value and returned.\n- Recursion solves problems by repeatedly dividing the work into smaller pieces that are more easily solved and then combining those pieces back together into a final solution.\n- A common recursive data structure is a tree, where elements (nodes) are connected to other nodes via edges in a parent-child relationship. The top of the tree is known as the \"root\" node, while the nodes at the very bottom are the \"leaf\" nodes.\n- A specific kind of tree is the binary tree, where every node has 0-2 children.\n- Trees can be implemented in Python in a variety of ways.\n- Inheritance is a feature of classes that allows the classes to share fields and behavior. When a class inherits from another class, the child class is the same type as the parent and includes the parent's fields in addition to the child's own fields.\n- One specific way to implement a tree in Python is to use inheritance and dataclasses.\n  - Create an empty base dataclass for a `Tree` that has no attributes.\n  - Create an instance of the `Tree` in a constant named `EMPTY_TREE`.\n  - Create another dataclass `BinaryTree` that inherits from `Tree` while providing three new fields: the `left` and `right` children (both `Tree` instances) and the `value` field (which holds the actual data of a node.)\n- The fact that the `BinaryTree` fields reference the `Tree` type is what makes these dataclasses recursive.\n- Recursive functions naturally operate over recursive structures like trees.\n","ip_ranges":"","name":"11B1) Recursion and Trees Reading","on_change":"","on_eval":"","on_run":"","owner_id":1,"owner_id__email":"acbart@udel.edu","points":0,"public":true,"reviewed":false,"sample_submissions":[],"settings":"{\n  \"youtube\": {\n    \"Bart\": \"Vh4fBECPxjQ\",\n    \"Amy\": \"gcEONv2ijFY\"\n  },\n  \"video\": {\n    \"Bart\": \"https://blockpy.cis.udel.edu/videos/bakery_advanced_recursion-Bart.mp4\",\n    \"Amy\": \"https://blockpy.cis.udel.edu/videos/bakery_advanced_recursion-Amy.mp4\"\n  },\n  \"small_layout\": true,\n  \"header\": \"Recursion and Trees\"\n}","starting_code":"","subordinate":true,"tags":[],"type":"reading","url":"bakery_advanced_recursion_read","version":11},"ip":"216.73.216.157","submission":{"_schema_version":3,"assignment_id":1123,"assignment_version":11,"attempts":0,"code":"","correct":false,"course_id":37,"date_created":"2026-05-20T12:51:53.421596+00:00","date_due":"","date_graded":"","date_locked":"","date_modified":"2026-05-20T12:51:53.421596+00:00","date_started":"","date_submitted":"","endpoint":"","extra_files":"","feedback":"","grading_status":"NotReady","id":2036881,"score":0.0,"submission_status":"Started","time_limit":"","url":"submission_url-eeb540ba-c2ae-4d50-8f8e-0103af6cc24a","user_id":2044663,"user_id__email":"","version":0},"success":true}