Recursive Algorithms with their types and implementation

Recursive Algorithms with their types and implementation

• 1.
  1 Recursive Algorithms Ahmad Baryal SabaInstitute of Higher Education Computer Science Faculty Oct 30, 2024
• 2.
  2 Table ofcontents  Recursion Algorithms  How Does Recursion Works?  Types of Recursion  When to Use Recursion?  Recursive vs Iterative Approaches  Advantages & Disadvantages of Recursion  Applications of Recursion Algorithms
• 3.
  Recursion Algorithms • Recursionis technique used in computer science to solve big problems by breaking them into smaller, similar problems. • The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function. Using a recursive algorithm, certain problems can be solved quite easily. 3
• 4.
  4 How DoesRecursion Work?  Recursion works by creating a stack of function calls. When a function calls itself, a new instance of the function is created and pushed onto the stack.  This process continues until a base case is reached, which is a condition that stops the recursion. Once the base case is reached, the function calls start popping off the stack and returning their results.  Recursive algorithms typically have two parts: 1. Base case: Which is a condition that stops the recursion. 2. Recursive case: Which is a call to the function itself with a smaller version of the problem.
• 5.
  5 Types ofRecursion There are several different recursion types and terms. These include: • Direct recursion: This is typified by the factorial implementation where the methods call itself. • In-Direct recursion: This happens where one method, say method A, calls another method B, which then calls method A. This involves two or more methods that eventually create a circular call sequence. • Head recursion: The recursive call is made at the beginning of the method. • Tail recursion: The recursive call is the last statement.
• 6.
  6 1.Direct Recursion Indirect recursion, a function calls itself directly. The classic example is calculating the factorial of a number. # Factorial using Direct Recursion def factorial(n): if n == 0 or n == 1: return 1 else: return n * factorial(n - 1) print(factorial(5)) # Output: 120 • Explanation: factorial(5) calls factorial(4), which calls factorial(3), and so on. • Use Case: Common in mathematical calculations.
• 7.
  7 2. IndirectRecursion In indirect recursion, two or more functions call each other in a circular way. For example, function A calls function B, and then B calls A. # Indirect Recursion Example def funcA(n): if n > 0: print("A:", n) funcB(n - 1) def funcB(n): if n > 0: print("B:", n) funcA(n - 1) funcA(3) # Output: A: 3, B: 2, A: 1 • Explanation: funcA calls funcB, which calls funcA again in a loop until n reaches zero. • Use Case: Less common but used in specific scenarios, such as mutual dependencies.
• 8.
  8 3. HeadRecursion In head recursion, the recursive call is made at the beginning of the function, before performing any other operations. # Head Recursion Example def head_recursion(n): if n > 0: head_recursion(n - 1) print(n) head_recursion(3) # Output: 1, 2, 3 • Explanation: The recursive call head_recursion(n-1) happens before print(n). • Use Case: Useful when processing steps need to happen after recursion unfolds.
• 9.
  9 4. TailRecursion In tail recursion, the recursive call is the last operation in the function, with no further operations after it. This allows some languages to optimize the recursion. # Tail Recursion Example def tail_recursion(n, accumulator=1): if n == 0: return accumulator else: return tail_recursion(n - 1, accumulator * n) print(tail_recursion(5)) # Output: 120 • Explanation: Tail recursion is optimized by some compilers to reduce memory usage. • Use Case: Often preferred for performance in large recursion depths.
• 10.
  10 When toUse Recursion?  Recursion is a powerful technique that can be used to solve a wide variety of problems. However, it is important to use recursion carefully, as it can lead to stack overflows if not used properly.  Recursion should be used when: • The problem can be broken down into smaller subproblems that can be solved recursively. • The base case is easy to identify. • The recursive calls are tail recursive.
• 11.
  11 Recursive vsIterative Approaches Recursive Approach • How it Works: Each function call waits for the next call to return, building up a stack of calls until reaching the base case (n <= 1). • Pros: Elegant and closely matches the mathematical definition. • Cons: Uses more memory due to stacked calls, which can lead to stack overflow for large n. Iterative Approach: • How it Works: Uses a loop to calculate the factorial, storing the result in a single variable, with no additional function calls. • Pros: More efficient in memory and avoids stack overflow. • Cons: Less intuitive for problems that are naturally recursive. def recursive_factorial(n): if n <= 1: return 1 return n * recursive_factorial(n - 1) def iterative_factorial(n): result = 1 for i in range(1, n + 1): result *= i return result
• 12.
  12 Advantages &Disadvantages of Recursion Advantages of Recursion: • Readability: Often results in cleaner, more readable code for complex problems. • Natural Fit for Tree/Graph Structures: Recursively explores branches of a tree or paths in a graph. • Ease in Solving Subproblems: Useful in problems like Fibonacci, permutations, or backtracking. Disadvantages of Recursion: • Performance Issues: Recursive calls add to the stack, which may lead to stack overflow. • Memory Usage: More memory-intensive due to multiple stack frames. • Alternative Approaches: Iterative solutions can sometimes be more efficient.
• 13.
  13 Applications ofRecursion Algorithms:  Here are some common applications of recursion: • Tree and Graph Traversal: Depth-first search (DFS) and breadth-first search (BFS) • Dynamic Programming: Solving optimization problems by breaking them into smaller subproblems • Divide-and-Conquer: Solving problems by dividing them into smaller parts, solving each part recursively, and combining the results • Backtracking: Exploring all possible solutions to a problem by recursively trying different options • Combinatorics: Counting or generating all possible combinations or permutations of a set
• 14.
  14 Any Questions?