RecursionWhat Is Recursion?FactorialDivide and Conquer AlgorithmsRecursion In ProgrammingDirect CallIndirect CallSlide 8Indirect Call (2)An Issue With Indirect RecursionProcedure Proc1 First?Procedure Proc2 First?Solution: Use A Dummy DefinitionSlide 14Requirements For RecursionExample ProgramSlide 17When To Use RecursionWhen To Consider Alternatives To RecursionDrawbacks Of RecursionBenefits Of Using RecursionCommon Pitfalls When Using RecursionNo Base CaseSlide 24No Progress Towards The Base CaseUsing Up Too Many ResourcesUndergraduate Definition Of RecursionJ. Michael MooreRecursionCSCE 110From James Tam’s materialJ. Michael MooreWhat Is Recursion?“the determination of a succession of elements (as numbers or functions) by operation on one or more preceding elements according to a rule or formula involving a finite number of steps” (Merriam-Webster online)J. Michael MooreFactorial•4! = 4 * 3 * 2 * 1•More formally•n! = n * (n-1) * (n-2) * … * 1J. Michael MooreDivide and Conquer Algorithms•Fractals (self similarity) http://www.pbs.org/wgbh/nova/fractals/scal-flash.html•Binary SearchJ. Michael MooreRecursion In Programming“a computer programming technique involving the use of a procedure, subroutine, function, or algorithm that calls itself one or more times until a specified condition is met at which time the rest of each repetition is processed from the last one called to the first”(Merriam-Webster online)J. Michael MooreDirect Callmoduleprocedure proc;begin : proc (); :end;J. Michael MooreIndirect Callm1m2J. Michael MooreIndirect Callm1m2m3…mnJ. Michael MooreIndirect Call (2)procedure proc1;begin : proc2;end;procedure proc2;begin : proc3;end;procedure proc3;begin : proc1;end;J. Michael MooreAn Issue With Indirect RecursionExample Scenario:Which one should be defined first?proc1 proc2proc2 proc1J. Michael Mooreprocedure proc1;begin:proc2;:end;procedure proc2;begin:proc1;:end;Procedure Proc1 First?What is proc2?J. Michael Mooreprocedure proc2;begin:proc1;:end;procedure proc1;begin:proc2;:end;Procedure Proc2 First?What is proc1?J. Michael MooreSolution: Use A Dummy DefinitionA "placeholder" for the compiler (definition comes later)Example problemprocedure proc1;begin:proc2;:end;procedure proc2;begin:proc1;:end;J. Michael MooreSolution: Use A Dummy DefinitionA "placeholder" for the compiler (definition comes later)Example problemprocedure proc2; FORWARD;procedure proc1;begin:proc2;:end;procedure proc2;begin:proc1;:end;J. Michael MooreRequirements For Recursion1) Base case2) Recursive stepJ. Michael MooreExample Programprogram factorialProgram (input, output);function factorial (num :integer):integer;begin if (num = 1) then factorial := 1 else factorial := num*factorial(num - 1);end;begin var number, nFactorial :integer; write('Enter the number for factorial :'); readln(number); nFactorial := factorial(number); writeln(number, '! = ', nFactorial);end.J. Michael Moorefactorial (1)if (1 = 1) then factorial := 1else factorial := 1 * factorial(1 – 1); factorial (3)if (3 = 1) then factorial := 1else factorial := 3 * factorial(3 – 1); factorial (2)if (2 = 1) then factorial := 1else factorial := 2 * factorial(2 – 1); User Types in 3nFactorial = factorial(3)126falsefalsetrueJ. Michael MooreWhen To Use Recursion•When a problem can be divided into steps.•The result of one step can be used in a previous step.•There is scenario when you can stop sub-dividing the problem into steps and return to previous steps.•All of the results together solve the problem.J. Michael MooreWhen To Consider Alternatives To Recursion•When a loop will solve the problem just as well•Types of recursion:•Tail recursion—A recursive call is the last statement in the recursive module.—This form of recursion can easily be replaced with a loop.•Non-tail recursion—A statement which is not a recursive call to the module comprises the last statement in the recursive module.—This form of recursion is very difficult to replace with a loop.J. Michael MooreDrawbacks Of RecursionFunction/procedure calls can be costly•Uses up memory•Uses up timeJ. Michael MooreBenefits Of Using Recursion•Simpler solution that’s more elegant (for some problems)•Easier to visualize solutions (for some people and certain classes of problems – typically require either: non-tail recursion to be implemented or some form of “backtracking”)J. Michael MooreCommon Pitfalls When Using Recursion•These three pitfalls can result in a segmentation fault occurring•No base case•No progress towards the base case•Using up too many resources (e.g., variable declarations) for each function callJ. Michael MooreNo Base Casefunction factorial (num : integer): integer;beginfactorial := num * factorial (num - 1);end;J. Michael MooreNo Base Casefunction factorial (num : integer): integer;beginfactorial := num * factorial (num - 1);end;When does it stop???J. Michael MooreNo Progress Towards The Base Casefunction factorial (num : integer): integer;begin if (num = 1) then factorial := 1 else factorial := num * factorial (num -1);end;J. Michael MooreUsing Up Too Many Resourcesprocedure proc;var arr : array [1..1000000] of char;beginproc;end;J. Michael MooreUndergraduate Definition Of RecursionWord: re·cur·sionPronunciation: ri-'k&r-zh&nDefinition: See recursionWav file from “The
View Full Document
Unlocking...