5.1.1 Identify a situation that requires the use of recursive thinking.


Recursion:
  • the repetition of an action, with an end that is controlled
    • data is created but not destroyed due to buffer overflow happening
      • Buffer overflow: overwriting due to lack of space
  • 2 ways of ending
    • calling itself
      • recursion happens from 0 - n
        • n! (factorial) - n x (n-1) x (n-2) x (n-3)!
        • includes n condition
        • factorial is recursion
    • stopping it manually (clicking, on/off switch)






5.1.2 Identify recursive thinking in a specified problem solution.

  • Binary trees:
    • way of organising data
      • if flipped over, organisation looks like a tree
      • drawn from top to bottom
    • data stored in nodes
      • starts with root
        • Root: the first node in the tree - the root has no parent
      • The tree is binary as two children are allowed - each node can have two links
        • left child
        • right child
      • Nodes with the same parent are siblings.
        • A node can only have one sibling.
      • Nodes which have no children are called leaves.
      • depth = height of tree
    • Givens:
      • Moving upward from any node will lead to the root.
      • One way to get from root to a particular node by following a sequence of links.
      • Every node has one parent, except for the root. (The root has no parent.)
    • Possibilities:
      • A node might have a left child, but not a right child.
    • Rules:
      1. The root does not have a parent.
      2. Every node has one parent.


    • Complete Binary trees

      • requires the nodes in each level to be filled from left-to-right before next level can be started
      • considered complete if all levels are full
        • full if there are 2 children or the node is a leaf
      • filled left-to-right
      • No Nodes is also a complete tree, as it is empty.
      • nearly complete tree if all levels, except the last are completely filled





Created By: Max Kossatz & Lucie Magister
Last update: 13/10/2014

Sources: