Iteration and Recursion (Section 6.5 – 6.6)Control Flow MechanismsIteration and RecursionIterationIteration Enumeration-controlled loopsSlide 6Slide 7Slide 8Iteration Access to Index Outside the LoopSlide 10Iteration IteratorsSlide 12Iterations IteratorsIteration Logically-Controlled LoopsRecursionSlide 16NondeterminacySlide 1811Iteration and RecursionIteration and Recursion(Section 6.5 – 6.6)(Section 6.5 – 6.6)CSCI 431 Programming LanguagesCSCI 431 Programming LanguagesFall 2003Fall 2003A compilation of material developed by Felix A compilation of material developed by Felix Hernandez-Campos and Michael ScottHernandez-Campos and Michael Scott22Control Flow MechanismsControl Flow Mechanisms•SequencingSequencing–Textual order, Precedence in ExpressionTextual order, Precedence in Expression•SelectionSelection•IterationIteration•Procedural abstractionProcedural abstraction•RecursionRecursion•ConcurrencyConcurrency•NondeterminacyNondeterminacy33Iteration and RecursionIteration and Recursion•These two control flow mechanism allow a computer These two control flow mechanism allow a computer to perform the same set of operations repeatedlyto perform the same set of operations repeatedly•They make computers usefulThey make computers useful–Go beyond the power of deterministic finite automataGo beyond the power of deterministic finite automata•Imperative languagesImperative languages mainly rely on iterations mainly rely on iterations•Functional languagesFunctional languages make more use of recursion make more use of recursion44IterationIteration•Iteration usually takes the form of Iteration usually takes the form of loopsloops•There are two principal varietiesThere are two principal varieties–Enumeration-controlledEnumeration-controlled loops loops»E.g.E.g. forfor (int i = 0; i <= 10; i++) { (int i = 0; i <= 10; i++) { … …}}–Logically controlledLogically controlled loops loops»E.g.E.g. int i = 0; int i = 0; whilewhile (i <= 10) { (i <= 10) { … … i++; i++; }}55IterationIterationEnumeration-controlled loopsEnumeration-controlled loops•Enumeration-controlled loopsEnumeration-controlled loops–Index variableIndex variable–Step size and boundsStep size and bounds–Body of the loopBody of the loop•Fortran I, II and IVFortran I, II and IV dodo 10 i = 1, 10, 2 10: i = 1 10 i = 1, 10, 2 10: i = 1... ...  … … i = i + 2i = i + 210: 10: continue if i <= 10 goto 10continue if i <= 10 goto 10–The value of i is tested at the end of the loopThe value of i is tested at the end of the loop»When When continuecontinue is reached is reached–Implementation is very fastImplementation is very fast»This statement is very close to assembly codeThis statement is very close to assembly code66IterationIterationEnumeration-controlled loopsEnumeration-controlled loops•Problems:Problems:–Loop boundaries must be integerLoop boundaries must be integer»Expressions are not allowedExpressions are not allowed–The index variable can change within the body of the loopThe index variable can change within the body of the loop–Goto statements may jump in and out of the loopGoto statements may jump in and out of the loop–The value of The value of ii after the termination of the loop is after the termination of the loop is implementation dependentimplementation dependent–The test of the loop takes place at the end, so the body is The test of the loop takes place at the end, so the body is executed at least onceexecuted at least once»Even if the lower bound is larger than the upper bound!Even if the lower bound is larger than the upper bound!77IterationIteration•Loop should Loop should check for empty check for empty boundsbounds•Code generationCode generation–OptimizationOptimization88IterationIteration•Backward loopsBackward loops–Previous code assumed a positive step sizePrevious code assumed a positive step size99IterationIterationAccess to Index Outside the LoopAccess to Index Outside the Loop•The value of the index variable at the end of loop is The value of the index variable at the end of loop is undefined in several languagesundefined in several languages–E.g.E.g. Fortran, Pascal Fortran, Pascal•Compilers can Compilers can fixfix this, but… this, but…–Generating slower codeGenerating slower code1010IterationIterationAccess to Index Outside the LoopAccess to Index Outside the Loop•The value of the index after the loop completes may The value of the index after the loop completes may not be validnot be valid–E.g.E.g.var c: ‘a’..’z’;var c: ‘a’..’z’;……for c:= ‘a’ to ‘z’ do beginfor c:= ‘a’ to ‘z’ do begin … …end;end;(* what comes after ‘z’? *)(* what comes after ‘z’? *)•In summary, even the simplest type of loop requires a In summary, even the simplest type of loop requires a good designgood design–You You willwill use language with poorly designed statements! use language with poorly designed statements!1111IterationIterationIteratorsIterators•Iterators generalize enumeration-controlled loopsIterators generalize enumeration-controlled loops–In the previous examples, the iteration was always over the In the previous examples, the iteration was always over the elements of an arithmetic sequenceelements of an arithmetic sequence•Iterators are used to enumerate the elements of any Iterators are used to enumerate the elements of any well-defined setwell-defined set–E.g.E.g. In Clu, In Clu,forfor i i inin from_to_by(first, last, step) from_to_by(first, last, step) dodo……endend–Notice some similarity to Perl’s foreach statementNotice some similarity to Perl’s foreach statement1212IterationIterationIteratorsIterators•Clu allows any set-like abstract data type to provide Clu allows any set-like abstract data type to provide an iteratoran iterator–E.g.E.g. integer iterator integer iterator1313IterationsIterationsIteratorsIterators•Iterators can also be based on object-oriented design Iterators can also be based on object-oriented design patternspatterns–Java’s Iterator interfaceJava’s Iterator interface» http://java.sun.com/docs/books/tutorial/collections/interfaces/collhttp://java.sun.com/docs/books/tutorial/collections/interfaces/collection.htmlection.html•Enumeration-controlled loops evolved significantly Enumeration-controlled loops