Recursion, Part 2

Return to List of Lectures

Previous Lecture

• Questions?
• Recursion Examples
  • Expressions as trees
    
    • An arithmetic expression is…
      • A constant, or
      • An expression “+” another expression
      • An expression “*” another expression
      • etc.
    • Represent as data objects containing members…
      • type (“const”, “+”, “*”, etc)
      • left, right (expression objects, if type ≠ “const”)
      • value (number, if type = “const”)
    • Evaluate an expression
      • Pseudocode
        

        value( root )
            if root.type = “const”
                return root.value
            else if root.type = “+”
                return value( root.left) + value( root.right )
            else if root.type = “*”
                return value( root.left ) * value( root.right )
            else if root.type = “sin”
                return sin( value( root.left ) )
            ...

      • Matlab and some runs
        

        function [ v ] = value( root )
        if strcmp( root.type, 'const' ) == 1
            v = root.value;
        elseif strcmp( root.type, '+' ) == 1
            v = value( root.left ) + value( root.right );
        elseif strcmp( root.type, '*' ) == 1
            v = value( root.left ) * value( root.right );
        elseif strcmp( root.type, 'sin' ) == 1
            v = sin( value( root.left ) );
        else
            display 'ERROR!';
        end
        end
        >> root = struct( 'type', '+' )
        root = 
            type: '+'
        >> arg1 = struct( 'type', 'const', 'value', 12 )
        arg1 = 
             type: 'const'
            value: 12
        >> arg2 = struct( 'type','const', 'value', 3 )
        arg2 = 
             type: 'const'
            value: 3
        >> root.left = arg1; root.right=arg2;
        >> value( root )
        ans =
            15
        >> exp2 = struct( 'type', 'sin' );
        >> arg3 = struct( 'type', 'const', 'value', 19 );
        >> exp2.left = arg3;
        >> root.right = exp2;
        >> value( root )
        ans =
           12.1499

    • Add node type “x”
    • Differentiate
      

      deriv( root )   // expression tree for root′
          if root.type = “const”
              return struct( “const”, 0 )
          else if root.type = “x”
              return struct( “const”, 1 )
          else if root.type = “*”
              return struct( “+”,
                             struct( “*”,
                                     deriv( root.left ),
                                     root.right ),
                             struct( “*”,
                                     root.left,
                                     deriv( root.right ) ) )
          else if root.type = “+”
              return struct( “+”, deriv( root.left ), deriv( root.right))
          else if root.type = “sin”
              return struct( “*”,
                             struct( “cos”, root.left ),
                             deriv( root.left ) )

      
      
    • Correctness by induction on structure of expression (structural induction)
      • Base cases: const, x
• Next
  • Calculating execution time of recursive algorithms
  • Read section 4.1

Next Lecture