12/05/20151SOLVING COMPUTATIONAL PROBLEMSUSING RECURSIVE ALGORITHMS YMGOVERVIEWIntroductionAlgorithms MatterWhat is RecursionRecursive Function & How they workHow to think Recursively (by example)Recursion and StackExample Applications? Calculating Factorials? Calculating Fibonacci Numbers? Other useful example File/directory listingWhen to use/not to use recursionSummaryFurther PracticeQuestions12/05/20152THE APPROACH TO COMPUTATIONAL SOLUTION? Common misconception: I know the language syntax so I can solve any given computationalproblem.? Common mistake: Writing code before fully understanding the problem.? Software solution development:? Do I understand the problem?? Start with the big picture: understand the problem and then dig into the details.? Understand the data of the problem instance.? Do I have the necessary information to solve the problem.? Understand algorithms.? Does the problem have a solution? If no solution is evident, reduce the problem to anotherproblem that has a solution.ALGORITHMS MATTER? Know your data structures and algorithms: which algorithm and datastructure to apply under which set of circumstances can make a bigdifference to the software produced.? Impact on runtime complexity and space requirements.? Thus the ability to choose an acceptable algorithm for the problem at handis a critical skill that any good software developer should have.? Its not about inventing new algorithms, but understanding which algorithms fitthe problem at hand balance the cost of the solution against the value itadds.12/05/20153WHAT IS RECURSION? A powerful way to solve large class of problems.? Involves decomposing the original problem into a series ofsimpler sub problems that are similar to the original problem.? Decomposition is continued until it yields sub problems thatcan be solved easily.? The solution to the original problem is obtained by combiningthe solutions of the sub problems.RECURSIVE FUNCTIONA function that calls itself (any function can call itself)When a function calls itself:? The system temporarily suspends execution of the current function, saves allthe information it needs to continue execution, and proceeds to evaluate therecursive call.? After every call, a new set of variables are created which do not affect thevariables that were created by the previous call to the function.? When the recursive call is completed, the result is passed to the previous calland so on to complete the computation.Foo()12/05/20154HOW DOES RECURSION WORKA recursive function must:?contain a conditional statement that will eventually cause it to exit(otherwise infinite loop & stack overflow)?call itself with a different value than when itself was called with.The case that causes the function to exit is called the base case.The logic of the function should be designed in such a way that thevalues passed to the recursive calls change in the direction of thebase case.The recursive algorithms we write generally consist of an IF statement:IF the stopping case is reached, then solve it.ELSE split the problem into simpler cases using recursion.WHAT MAKES RECURSION WORKProblems that can be solved by recursion have these characteristics:?Must have recursive structure, i.e. the problem solution is similar for a largeinput as well as small input size.?One or more stopping cases have a simple, nonrecursive solution.?The other cases of the problem can be reduced (using recursion) toproblems that are closer to stopping cases.?Eventually the problem can be reduced to only stopping cases, which arerelatively easy to solve.?The solution to the smaller problem must help in solving the biggerproblem.Many programming problems exhibit this kind of behaviour.12/05/20155DEVELOPING THE ALGORITHM STEPS1. Understand how the algorithm works first in an abstract sense2. Define what the recursive function should do (unfortunately overlooked ? ) and write aprototype for it.3. Try to express the problem as a simpler version of itself.4. Determine the stopping cases (the base case) there may be more than one and itssolution(s).5. Determine the recursive steps (smaller problems to solve).6. Use the solutions of the smaller problem to solve the larger problem.HOW TO THINK RECURSIVELYREMEMBER: Recursion solves a big problem by solving one or more smaller problems anduses the solutions of the smaller problem to solve the bigger problem.E.g. a*n= (a + a + a + . ) n copies of a= a + (a + a + a + ) n-1 copies of a= a+ a*(n-1)Reducing the problem to simpler or smaller version of the same problem plus some simplecomputations: Recursive stepKeep reducing until you reach a simple step that can be solved directly: Base casea*n = a if n =1 (base case)a*n = a + a*(n-1) (recursive case)12/05/20156MULTIPLY RECURSIVELY THE ALGORITHMint Multiply(int a , int n){if (n ==1)return a;elsereturn a + Multiply (a, n-1);}int Multiply(in
t a , int n){return a*n;}BASICS OF STACK AND HEAP?When a program is executed, it is provided with stack and heap memory.?Stack memory: for storing values of primitive data types (int, double,bool, etc.).?Heap memory: for storing values of reference types (class objects etc.).?Function calls also have memory requirements To store values forparameters, local variables, and an address for a return value.?This memory comes from the stack during the function execution.?After the function has completed, the memory is released back to thestack.12/05/20157A LOOK INTO THE STACKEvery call to a method creates a new set of local variables on the stack and aredeleted when the method returnsActivation records1. parameters of the method arepushed onto the stack2. The return address is pushedonto the stack3. The top-of-stack index isincremented by the totalamount of memory required bythe local variables within themethod4. A jump is made to the methodRECURSION AND STACK?During recursion, function calls continue to require more and morestack memory which does not get released until the recursive chainterminates.?Stack overflow results when memory allocations are beyond whatthe stack is able to provide.?So if a function has too many levels of recursive calls, one can runout of memory.12/05/20158THE FACTORIALThe factorial (!) of a positive integer number is the number multiplied by the product of allpositive integers less than that number.n! = n*(n-1)*(n-2) * .1Base Case: 0! = 1, Recursive case: Assume you know (n-1)! Then use that to find n!.E.g. 5! = 5*4*3*2*1 = 120.5! = 5*4!4! = 4*3!3! = 3*2!2! = 2*1!1! = 1*0! 0! = 1Returning values chain Calling chain THEFACTORIAL?An iterativealgorithm uses alooping construct.?A recursivealgorithm uses abranchingstructure.12/05/20159WATCHING THE STACKa = 5Initial a = 5Return to calla = 4 After 1 recursion a = 5Return to calla = 4Return to calla = 3Return to calla = 2Return to calla = 1 After 4th recursion Every call to the method creates a new set of local variables! a = 5Return to calla = 4Return to calla = 3Return to calla = 2Return to calla = 1 After 4th recursion a = 5Return to calla = 4Return to calla = 3Return to calla = 2*1 = 2 a = 5Return to calla = 4Return to calla = 3*2 = 6 a = 5Return to calla = 4*6 = 24 a = 5*24 = 120ResultStack pointerStack pointerStack pointerStack pointerUnwinding the Activation Call1. The top-of-stack index is decremented by thetotal amount of memory consumed by themethod2. The return address is popped off the stack3. The top-of-stack index is decremented by thetotal amount of memory consumed by the actualparametersSTACK OVERFLOW :The default stack size for.NET applications is 1MB(1024*1024)/85334~12bytes for eachrecursive function call12/05/201510THE FIBONACCINUMBERSThe Fibonacci numbers arethe numbers in the followingsequence:? 0,1,1,2,3,5,8,13,21,34,55, ? Where every element is the sumof the previous two.? f0=0? f1 =1? then F[n] = f[n-2] + f[n-1]APPLICATION EXAMPLE DIRECTORY TREE12/05/201511WHEN TO USE RECURSIONWhen compared to iterative approach:?Recursion usually produces compact solution (fewer lines of code).?Easier to debug & Easier to prove by induction.Because writing algorithms is hard, but testing algorithms is harder.So should we use it all the time where possible??Use it when the depth of recursive calls is relatively shallow (can be as efficient as the nonrecursive version).?BUT Recursive solutions can be very inefficient in time and space (see Fibonacci example).?The main drawback with recursion is that it can use O(n) stack space when a simple loopmay use O(1).?The use of recursion should always be considered for fast algorithms (avoid it for algorithmswith O(n^2) run time complexities.?Nearly every recursively defined problem can be solved iteratively. Fibonacci Numbers Time comparisonNo.Iterative (ms)Recursive(ms)1000150120352561130510835610464077525459771615010797,230 SUMMARY?Recursion is a powerful divide and conquer programming tool.?Provides a simpler and readable algorithmic structure.?Has its costs (space and time complexity) and can not be used without boundaries.?Can be replaced by iteration for reasons of efficiency and thus a compromise mustbe reached between code readability and performance.?Function calls (recursive or otherwise) require stack memory for local variables,parameters, return variable address and function overhead.?Note that some data structures and problems are recursive by nature (e.g. tree datastructure, merge sort, quick sort) thus candidates for recursion.?And remember all good recursion must come to an end sooner or later (the need forbase case).12/05/201512There are many interesting problems that can be solved by recursion.Create a recursive function for the following:?f(x) = x?GCD (Euclidean)?Sorting algorithms? Pretty GraphicsFURTHER PRACTICEn