CS 131 LECTURE 3 - RECURSIVE SUBPROGRAMS AND PROGRAM EFFICIENCY

Iterative Definition Of Triangular Numbers

Iterative Evaluation Of Triangular Numbers

Iterative Triangular Function

FUNCTION Triangular(Number: Positive)
RETURN Positive IS
  Sum: Integer := 0;
BEGIN
  FOR Index IN 1..Number LOOP
    Sum := Sum + Index;
  END LOOP;
  RETURN Sum;
END Triangular;

Important Points:

1. The Triangular Number Sequence Is The Following:

1, 3, 6 ,10, 15, 21, 28, 36 ...

2. The Summation Symbol Of Mathematics Corresponds To The For Loop Of Ada

Recursive Definition Of Triangular Numbers

Recursive Evaluation Of Triangular Numbers

Recursive Triangular Function

FUNCTION Triangular(Number: Positive)
RETURN Positive IS
BEGIN
  IF Number = 1 THEN
    RETURN 1;
  ELSE
    RETURN Number + Triangular(Number-1);
  END IF;
END Triangular;

Important Point:

1. The Recursive Ada Function Is Simply A Translation Of The Recursive Definition

Palindrome(s) =, where n = Length(s)

Palindrome(s) =

( " Is Equivalent To An Iterative Ù )

Iterative Evaluation Of Palindrome

Palindrome(abbcba) = (a = a) Ù (b = b) Ù (b = c) = True Ù True Ù False = False

Iterative Palindrome Function

FUNCTION Palindrome(Word: String)
RETURN Boolean IS
  Right: Integer;
BEGIN
  FOR Index IN Word'First..Word'Last/2 LOOP
    Right := Word'Last - Index + 1;
    IF Word(Index) /= Word(Right) THEN
      RETURN False;
    END IF;
  END LOOP;
  RETURN True;
END Palindrome;

Recursive Definition Of Palindrome

Recursive Evaluation Of Palindrome

Palindrome(abbcba) = (a = a) Ù Palindrome(bbcb)

= True Ù Palindrome(bbcb)
= True Ù (b = b) Ù Palindrome(bc)
= True Ù True Ù Palindrome(bc)
= True Ù True Ù (b = c)
= True Ù True Ù False = False

Recursive Palindrome Function

FUNCTION Palindrome(Word: String)
RETURN Boolean IS
BEGIN
  IF Word'Length <= 1 THEN
    RETURN True;
  ELSE
    RETURN
      Word(Word'First) = Word(Word'Last)
    AND THEN
      Palindrome(Word(Word'First+1 ..
        Word'Last-1));
  END IF;
END Palindrome;

Important Points:

1. Recursion Provides The Beginning Of A Functional Style Of Programming That Is Characterized By:

a) No Local Variables
b) No Intermediate States
c) No Assignment Statements

2. Functional Programming Is At A Higher Level Of Abstraction Than Imperative Programming

3. Thinking Recursively Means Searching For A Definition, Not For An Algorithm

4. Recursion Can Often Provide Shorter Simpler Solutions

Fibonacci Function

FUNCTION Fibonacci(Number: Natural)
RETURN Natural IS
BEGIN
  IF Number = 0 OR Number = 1 THEN
    RETURN Number;
  ELSE
    RETURN Fibonacci(Number-1) +
      Fibonacci(Number-2);
  END IF;
END Fibonacci;

Reversal Procedure

WITH Text_IO;
PROCEDURE Reversal IS
  Char: Character;
BEGIN
  IF NOT Text_IO.End_Of_Line THEN
    Text_IO.Get(Char);
    Reversal;
    Text_IO.Put(Char);
  END IF;
END Reversal;

Important Points:

1. This Procedure Uses The Compiler's Stack Of Activation Records To Perform The Reversal

2. The Order Of Execution Is That All The Gets Are Executed Before All The Puts

Major Issues:

1. Efficiency Means Efficient Use Of Machine Resources

a) CPU Time

b) Memory

2. Efficiency Can Be Determined In Two Ways

a) Empirically

Run Program With Many Different Data Sets A Graph Performance For Each Case

b) Analytically

Count Lines Of Code Executed To Determine A Formula For Performance

3. Precise Determination Of Efficiency Is Generally Unnecessary, General Behavior Usually Suffices

Big-O Is A Measure Of General Behavior

4. Performance Can Depend On Input Data, For Some Algorithms Multiple Measurements Are Required

a) Worst Case

b) Average Case

c) Best Case

Linear Search Procedure

WITH Text_IO;
PROCEDURE Linear_Search IS
  SUBTYPE Bounds IS INTEGER RANGE 1..10;
  Table: ARRAY(Bounds) OF Integer :=
    (31,15,8,34,5,81,2,97,30,95);
  Value: Integer;
  Found: Boolean;
  PACKAGE Int_IO IS NEW Text_IO.Integer_IO
    (Integer);
BEGIN                                   Best    Worst
  Text_IO.Put("Enter Value: ");         1       1
  Int_IO.Get(Value);                    1       1
  FOR Index IN Bounds LOOP              1       n
    Found := Table(Index) = Value;      1       n
    EXIT WHEN Found;                    1       n
  END LOOP;                             0       n
  Text_IO.Put("It Is ");                1       1
  Text_IO.Put(Boolean'Image(Found));    1       1
  Text_IO.Put("Value Is In Table");     1       1
  Text_IO.New_Line;                     1       1
END Linear_Search;

Important Point:

1. The Execution Time For This Procedure Increases Linearly With The Size Of The Table In The Worst Case

Execution Time Function For Linear Search-Worst Case

f(n) = 4n + 6, Where n Is The Table Size

Formal Definition Of Big-O:

f(n) Î O(g(n)) If And Only If There Exist Two Constants m and n0 such that |f(n)| ² m|g(n)| for n ² n0

Big-O Proof

4n + 6 Î O(n) Because |4n + 6| ² 10|n| for n ² 1

Important Point:

1. The Big-O Function g Is An Eventual (After n0), Proportional (By A Factor Of m) Upper Bound Of The Efficiency Function f

DETERMINING BIG-O

Polynomial Theorem

If f(x) = a_nxⁿ + a_n-1x^n-1 + ... + a₁x + a₀ Where aⁿ ² 0 Then f(x) Î O(x^m) " m ² n

Applying The Polynomial Theorem

f(x) = 3x3 + 5x2 + 4x + 8

f(x) Î O(x3), f(x) Î O(x4), f(x) Î O(x5) ...

Important Point:

1. Every Function Has Many Big-O Upper Bounds, The Least Big-O Upper Bound Is Of Greatest Interest

x³ Is The Least Big-O For 3x³ + 5x² + 4x + 8

Determining The Least Big-O For Polynomials

1. Drop All But The Highest Order Term

2. Drop All Constants

Comparing Big-O For Polynomials

O(x) Í O(x²) Í O(x³) Í O(x⁴) ...

Comparing Big-O For Polynomials With Other Functions

O(log² x) Í O(x) Í O(x log₂ x) Í O(x²) Í O(2^x)

O(log₂ x) Is Most Efficient, O(2^x) Is Least Efficient

Single Loop

O(n)

FOR i IN 1..n LOOP
  ...
END LOOP;

Sequential Loops

2 ´ O(n) = O(n)

FOR i IN 1..n LOOP
  ...
END LOOP;
FOR j IN 1..n LOOP
  ...
END LOOP;

Nested Loops

O(n²)

FOR i IN 1..n LOOP
  FOR j IN 1..n LOOP
    ...
  END LOOP;
END LOOP;

Important Points:

1. Divide And Conquer Approaches Produce Logarithmic Efficiency

2. Doubly Recursive Algorithms, Such As Fibonacci Numbers, Have Exponential Efficiency

Important Points:

1. The Use Of Recursion Can Dramatically Reduce The Efficiency Of Certain Problems

2. Other Problems Such As Character Reversal, Can Not Be Solved In A Bounded Memory Space, For Such Problems Recursion Does Not Introduce An Efficiency Penalty