Recursion-and-Backtracking.pdf

DATA STRUCTURES AND ALGORITHM Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing RECURSION AND BACKTRACKING Prepared by: Maxil S. Urocay MSCS ongoing RECURSION Prepared by: Maxil S. Urocay MSCS ongoing  RECURSION - Is a programming technique where...

DATA STRUCTURES AND ALGORITHM Prepared by: Maxil S. Urocay MSCS ongoing Prepared by: Maxil S. Urocay MSCS ongoing RECURSION AND BACKTRACKING Prepared by: Maxil S. Urocay MSCS ongoing RECURSION Prepared by: Maxil S. Urocay MSCS ongoing  RECURSION - Is a programming technique where a function calls itself in order to solve smaller instances of the same problem. - is defined as a process which calls itself directly or indirectly and the corresponding function is called a recursive function. *A recursive function is one that calls itself until a base case is reached, at which point the function returns a value. *It is used to solve problems that can be broken down into smaller and subproblems, which are then solved recursively. Prepared by: Maxil S. Urocay MSCS ongoing  TWO PARTS OF RECURSION *BASE CASE which cannot be expressed in terms of smaller version of itself, and the condition which the recursion stops. *RECURSIVE CASE which can be expressed in terms of smaller versions of itself. This is where the functions calls itself with a modified argument, moving towards the base case. Prepared by: Maxil S. Urocay MSCS ongoing  STEPS FOR WRITING RECURSION ALGORITHM 1. Define the base case 2. Define the recursive case 3. Write the function 4. Call the function 5. Handle the return values Prepared by: Maxil S. Urocay MSCS ongoing  TYPES OF RECURSION 1.Direct recursion – When a function is called within itself directly and mostly categorized into four types (tail, head, tree and nested recursion). Prepared by: Maxil S. Urocay MSCS ongoing  EXAMPLE A function to calculate the factorial of a number. The factorial of a non-negative integer n is defined as: n! = n x (n - 1)! for n > 0 //recursive case that defines how function calls itself for smaller values 0! = 1 //base case which the conditions stops the recursion Prepared by: Maxil S. Urocay MSCS ongoing  EXAMPLE n! = n x (n - 1)! for n > 0 To calculate 5! Substituting it back: 5! = 5 x 4! 1! = 1 x 1 = 1 4! = 4 x 3! 2! = 2 x 1 = 2 3! = 3 x 2! 3! = 3 x 2 = 6 2! = 2 x 1! 4! = 4 x 6 = 24 1! = 1 x 0! 5! = 5 x 24 = 120 0! = 1 5! = 120 Prepared by: Maxil S. Urocay MSCS ongoing public class Factorial { public static int factorial(int n) { if (n == 0) { return 1; // Base case } return n * factorial(n - 1); // Recursive case } } //STANDARD CODE FOR DIRECT RECURSION Prepared by: Maxil S. Urocay MSCS ongoing  TYPES OF RECURSION TAIL RECURSION the function makes recursive calling itself, and that recursive call is the last statement executes by the function. After that, there is no function, or statement is left to call the recursive function. Prepared by: Maxil S. Urocay MSCS ongoing  EXAMPLE CODE for TAIL RECURSION public class FactorialTail { public static int factorial(int n) { return factorialHelper(n, 1); } private static int factorialHelper(int n, int accumulator) { if (n == 0) return accumulator; return factorialHelper(n - 1, n * accumulator); } Prepared by: Maxil S. Urocay MSCS ongoing  TYPES OF RECURSION HEAD RECURSION also called as non-tail recursive which a function makes a recursive call itself, the recursive call will be the first statement in the function. It means there should be no statement or operation is called before the recursive calls. Furthermore, the head recursive does not perform any operation at the time of recursive calling. Instead, all operations are done at the return time. Prepared by: Maxil S. Urocay MSCS ongoing  EXAMPLE CODE for HEAD RECURSION public class FactorialHead { public static int factorial(int n) { if (n == 0) return 1; return factorial(n - 1) * n; } Prepared by: Maxil S. Urocay MSCS ongoing  TYPES OF RECURSION NESTED RECURSION A function is called the tree recursion, in which the function makes more than one call to itself within the recursive function. Prepared by: Maxil S. Urocay MSCS ongoing  EXAMPLE CODE for HEAD RECURSION public class FactorialNested { public static int factorial(int n) { if (n == 0) return 1; return n * factorial(nested(n - 1)); } private static int nested(int n) { if (n == 0) return 1; return factorial(n - 1); } Prepared by: Maxil S. Urocay MSCS ongoing  TYPES OF RECURSION 2. Indirect recursion – occurs when a function calls another function that eventually calls the original function and it forms a cycle. Prepared by: Maxil S. Urocay MSCS ongoing  EXAMPLE CODE for HEAD RECURSION static int factorial(int n) { if (n == 0) { return 1; } else { return multiply(n, factorial(n - 1)); } } static int multiply(int a, int b) { return a * b; } Prepared by: Maxil S. Urocay MSCS ongoing  RECURSION APPLICATION - can be used in many fields which includes Searching and Sorting algorithms, Mathematical calculations, Compiler design, Graphics, Artificial intelligence and more. Prepared by: Maxil S. Urocay MSCS ongoing BACKTRACKING Prepared by: Maxil S. Urocay MSCS ongoing  BACKTRACKING - are like problem-solving strategies that help explore different options to find the best solution. - allows us to systematically try all available avenues from a certain point after some of them lead to nowhere. - was first introduced by Dr. D.H Lehmer in 1950’s. R.J Walker was the first man who gave algorithmic description in 1960. Later developed by S. Golamb and L. Baumert. Prepared by: Maxil S. Urocay MSCS ongoing  BACKTRACKING - commonly used in situations where you need to explore multiple possibilities to solve a problem, like searching for a path in a maze or solving a puzzles like Sudoku. *When a dead end is reached, the algorithm backtracks to the previous decision point and explores a different path until a solution is found or all possibilities have been exhausted. Prepared by: Maxil S. Urocay MSCS ongoing BACKTRACKING Prepared by: Maxil S. Urocay MSCS ongoing  STEPS FOR BACKTACKING ALGORITHM 1. Define the problem 2. Choose a representation 3. Define the state space 4. Define the initial state 5. Define the goal state 6. Implement the search 7. Check for termination 8. Optimize the algorithm Prepared by: Maxil S. Urocay MSCS ongoing  BACKTRACKING C D B A E F G H I INITIAL STATE: A GOAL STATE: I STATE SPACE: A, B, C, D, C, B, E, F, E, B, A, G, H, I - 13 steps (Linear search) with O(n) time complexity Prepared by: Maxil S. Urocay MSCS ongoing  THANK OFFERS PRODUCT YOU Prepared by: Maxil S. Urocay MSCS ongoing