CMSC 132: Object-Oriented Programming IIRecursive AlgorithmsDepartment of Computer ScienceUniversity of Maryland, College ParkRecursionRecursion is a strategy for solving problemsA procedure that calls itselfApproachIf ( problem instance is simple / trivial )Solve it directlyElse1. Simplify problem instance into smallerinstance(s) of the original problem2. Solve smaller instance using same algorithm3. Combine solution(s) to solve original problemRecursive Algorithm Format1. Base caseSolve small problem directly2. Recursive stepSimplify problem into smaller subproblem(s)Recursively apply algorithm to subproblem(s)Calculate overall solutionExample – FindTo find an element in an array Base caseIf array is empty, return falseRecursive stepIf 1stelement of array is given value, return trueSkip 1stelement and recur on remainder of arrayExample – CountTo count # of elements in an arrayBase caseIf array is empty, return 0Recursive stepSkip 1stelement and recur on remainder of arrayAdd 1 to resultExample – Factorial Factorial definitionn! = n n-1 n-2 n-3 … 3 2 10! = 1To calculate factorial of nBase caseIf n = 0, return 1Recursive stepCalculate the factorial of n-1Return n (the factorial of n-1)Example – Factorial Codeint fact ( int n ) {if ( n == 0 ) return 1; // base casereturn n * fact(n-1); // recursive step}PropertiesRecursion relies on the call stackState of current procedure is saved when procedure is recursively invokedEvery procedure invocation gets own stack spaceAny problem solvable with recursion may be solved with iteration (and vice versa)Use iteration with explicit stack to store stateAlgorithm may be simpler for one approachRecursion vs. IterationRecursive algorithmint fact ( int n ) {if ( n == 0 ) return 1;return n * fact(n-1);}Recursive algorithm is closer to factorial definitionIterative algorithmint fact ( int n ) {int i, res;res = 1;for (i=n; i>0; i--) {res = res * i;}return res;}Example – Towers of HanoiProblemMove stack of disks between pegsCan only move top disk in stackOnly allowed to place disk on top of larger diskExample – Towers of HanoiTo move a stack of n disks from peg X to YBase caseIf n = 1, move disk from X to YRecursive step1. Move top n-1 disks from X to 3rdpeg2. Move bottom disk from X to Y3. Move top n-1 disks from 3rdpeg to YIterative algorithm would take much longer to describe!Recursion vs. IterationIterative algorithmsMay be more efficientNo additional function callsRun faster, use less memoryRecursion vs. IterationRecursive algorithmsHigher overheadTime to perform function callMemory for call stackMay be simpler algorithmEasier to understand, debug, maintainNatural for backtracking searchesSuited for recursive data structuresTrees, graphs…Making Recursion WorkDesigning a correct recursive algorithmVerify1. Base case isRecognized correctlySolved correctly2. Recursive case Solves 1 or more simpler subproblemsCan calculate solution from solution(s) to subproblemsUses principle of proof by inductionRequirementsMust haveSmall version of problem solvable without recursionStrategy to simplify problem into 1 or more smaller subproblemsAbility to calculate overall solution from solution(s) to subproblem(s)Proof By InductionMathematical techniqueA theorem is true for all n 0 if1. Base caseProve theorem is true for n = 0, and2. Inductive stepAssume theorem is true for n (inductive hypothesis)Prove theorem must be true for n+1Types of RecursionTail recursionSingle recursive call at end of functionExampleint tail( int n ) {…return function( tail(n-1) );}Can easily transform to iteration (loop)Types of RecursionNon-tail recursionRecursive call(s) not at end of functionExampleint nontail( int n ) {…x = nontail(n-1) ;y = nontail(n-2) ;z = x + y;return z;}Can transform to iteration using explicit stackPossible Problems – Infinite Loop Infinite recursionIf recursion not applied to simpler problemint bad ( int n ) {if ( n == 0 ) return 1;return bad(n);}Will infinite loop Eventually halt when runs out of (stack) memoryStack overflowPossible Problems – Efficiency May perform excessive computationIf recomputing solutions for subproblemsExampleFibonacci numbersfibonacci(0) = 1 fibonacci(1) = 1 fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)Possible Problems – Efficiency Recursive algorithm to calculate fibonacci(n)If n is 0 or 1, return 1Else compute fibonacci(n-1) and fibonacci(n-2)Return their sumSimple algorithm exponential time O(2n)Computes fibonacci(1) 2n timesCan solve efficiently using IterationDynamic programming Will examine different algorithm strategies later…Examples of Recursive AlgorithmsBinary searchQuicksortN-queensFractalsN-QueensGoalPlace queens on a board such that every row and column contains one queen, but no queen can attack another queenRecursive approach To place queens on NxN boardAssume you’ve already placed K queensFractalsGoalConstruct shapes using a simple recursive definition with a natural appearancePropertiesAppears similar at all scales of magnification Therefore “infinitely complex”Not easily described in Euclidean geometryMandelbrot
View Full Document
Unlocking...