3-2-2 Recursion

Recursion describes the ability of a routine to call itself. This means a recursive routine is defined in terms of itself.

General case: the solution in terms of itself for a value of n.
Base case: a value that has a solution which does not involve any reference to the general case solution.

An example of a recursive routine would be n factorial.

function factorial is: input: integer n such that n >= 0 output: [n × (n-1) × (n-2) × … × 1] 1. if n is 0, return 1 2. otherwise, return [ n × factorial(n-1) ] end factorial The general case is n! = n * (n-1)! The base case is 1! = 1

Recursion works only if the routine is called with the current value or values passed as parameters. It would not work with global variables.

Each time a routine is called, a special area of main memory, called the stack, is used. There the return address is stored as well as the contents of registers. Any local variables and the routine's parameters are also known as a stack frame. When a routine ends, control normally passes to the stored return address and its stack frame is removed from the stack.

Stack Frame: the locations in the stack area used to store the values referring to one invocation of a routine.

Towers of Hanoi: Example

3-2-1 Programming Paradigms

Program Language: a notational system for describing computation in a machine readable and human readable form.

• 1GL: Machine Code
• 2GL: Assembly Language
• 3GL: Imperative/Procedural Language (Machine Independent) (Fortran, Pascal, C)
• 4GL+: Event Driven and Object Oriented Language

Paradigms: dividing 3GL & 4GL languages into different styles or methodologies of language.

Imperative/Procedural :	program = algorithms + data good for decomposition
Functional :	program = functions o functions good for reasoning
Logic programming :	program = facts + rules good for searching
Event-Driven :	program = GUI + algorithms + data great for visual development
Object-oriented :	program = objects + messages good for modeling(!)
Brief Chronology of 3GL and 4GL Programming Languages:   Early 1950s “order codes” (primitive assemblers) 1957 FORTRAN the first high-level programming language 1958 ALGOL the first modern, imperative language 1960 LISP, COBOL Interactive programming; business programming 1962 APL, SIMULA the birth of OOP (SIMULA) 1964 BASIC, PL/I 1966 ISWIM first modern functional language (a proposal) 1970 Prolog logic programming is born 1972 C the systems programming language 1975 Pascal, Scheme two teaching languages 1978 CSP Concurrency matures 1978 FP Backus’ proposal 1983 Smalltalk-80, Ada OOP is reinvented 1984 Standard ML FP becomes mainstream (?) 1986 C++, Eiffel OOP is reinvented (again) 1988 CLOS, Oberon, Mathematica 1990 Haskell FP is reinvented 1990s Perl, Python, Ruby, JavaScript Scripting languages become mainstream 1995 Java OOP is reinvented for the internet 2000 C# Fortran History John Backus (1953) sought to write programs in conventional mathematical notation, and generate code comparable to good assembly programs No language design effort (made it up as he went along) Most effort spent on code generation and optimization FORTRAN I released April 1957; working by April 1958 Current standard is FORTRAN 2003 (FORTRAN 2008 WIP) Innovations Symbolic notation for subroutines and functions Assignments to variables of complex expressions DO loops Comments Input/Output formats Machine-independence Successes Easy to learn; high level Promoted by IBM; addressed large user base (scientific computing) ALGOL 60 History Committee of PL experts formed in 1955 to design universal, machine-independent, algorithmic language First version (ALGOL 58) never implemented; criticisms led to ALGOL 60 Innovations BNF (Backus-Naur Form) introduced to define syntax (led to syntax-directed compliers) First block-structured language; variables with local scope Structured control statements Recursive procedures Variable size arrays Successes Highly influenced design of other PLs but never displaced FORTRAN COBOL History Designed by committee of US computer manufacturers Targeted business applications Intended to be readable by managers Innovations Separate descriptions of environment, data and processes Successes Adopted as de facto standard by US DOD Stable standard for 25 years Still the most widely used PL for business applications PL History Designed by committee of IBM and users (early 1960s) Intended as (large) general-purpose language for broad classes of applications Innovations Support for concurrency (but not synchronization) Exception-handling on conditions Successes Achieved both run-time efficiency and flexibility (at expense of complexity) First "complete" general purpose language Functional Languages: SWIM (If you See What I Mean) >Peter Landin (1966) — paper proposal FP >John Backus (1978) — Turing award lecture ML >Edinburgh >initially designed as meta-language for theorem proving >Hindley-Milner type inference >“non-pure” functional language (with assignments/side effects) Miranda, Haskell >“pure” functional languages with “lazy evaluation”

Prolog

History

• Originated at U. Marseilles (early 1970s) and compliers developed at Marseilles and Edinburgh (mid to late 1970s)

Innovations

• Theorem proving paradigm
• Programs as sets of clauses: facts, rules and questions
• Computation by "unification"

Successes

• Prototypical logic programming language
• Used in Japanese Fifth Generation Initiative

Object-Oriented Languages - a problem is broken down into objects which contain data and processes.



Left: Inheritance Diagram. Right: Objects/Attributes/Methods.



Object Oriented Programming Terms:

ØObject   A real world item which we store data about

ØClass  Groups of objects with the same attributes and methods

ØBase Class   Top class in the Inheritance Diagram

ØSub Class   Stores attributes and methods of parent class, and adds some

   of its own

ØInheritance  Is where sub class take the attributes and methods of a

   parent class

ØPolymorphism  One class morphs into multiple subclasses

ØContainment  A class contains attributes and methods in one unit

ØBundle  Bundle together attributes and methods

ØInstance  An object is an instance of a class

ØEncapsulation  Bundles methods and data