Recursion in Data Structure

Recursion is a technique in programming where a function calls itself to solve smaller instances of the same problem. It involves two main components: the base case and the recursive case. The base case is the condition that stops the recursive calls, preventing infinite loops. The recursive case is where the function continues to call itself, breaking the problem down into smaller parts. For example, calculating the factorial of a number can be done using recursion, where `n! = n * (n-1)!` with `0! = 1` as the base case.

In data structures, recursion is commonly used for tasks like traversing or searching through trees and linked lists. It simplifies complex problems by dividing them into more manageable subproblems. For instance, in binary trees, recursive methods are used for traversals such as Preorder, Inorder, and Postorder, which visit nodes in a specific order using recursive function calls.

1. Recursion in Data Structure Presented By: Basit Ali Soomro Khuda Bux Magsi

2. Agenda Introduction of Recursion Types of Recursion Base Case and Recursive Case Advantages & Disadvantages of Recursion Recursive Algorithms Recursion in Data Structure Time and Space Complexity of Recursive Algorithms Conclusion 2

3. Objective: “The objective of the presentation is to clearly explain the topic of recursion to you.” 3

4. Magic: Imagine a function that solves a problem by breaking it down into smaller parts and solving each part one by one . 4 That's the magic of recursion.

5. Recursion: “Recursion is a technique where a function calls itself directly or indirectly.” Directly: when a function calls itself in its definition. Indirectly: when a function call another function and that function call the first function. Example: Function A calls function B and Function B is calling Function A again. 5

6. Direct Function Call: 6

7. Indirect Function Call: 7

8. Why Do We Use Recursion? “ When we have a complex problem that relies on solving a smaller problem of the same type, We Use Recursion . ” Example: # 1:  When tracing your family history, you might ask your parents about their parents, and then ask your grandparents about their parents, and so on. This process can be seen as recursive because you're asking the same question (about parents) repeatedly, but going back further in time with each iteration. Eventually, you'll reach ancestors who have no living relatives to ask about.. 8

9. Example: # 2: 2 4 = 2 x 2 x 2 x 2. 2 4 = 2 x 2 3 2 3 = 2 x 2 2 2 2 = 2 x 2 Here it seems that the solution to a large problem depends on solving a smaller problem of the same type. 9

10. Components of Recursion: There are two important component of Recursion. Mandatory. 2) Optional.

11. 1) Mandatory : Recursion contain two mandatory things. 1) Base Case: It is a specific condition within a function that stops the recursive calls and allows the function to return a final value 2) Recursion Relation: The Function Call. 11

12. 2) Optional : Optional can contains many things. 1)Storing data, 2) Printing something 3)Updating date, & so on.. 12

13. Tail & Head Recursion. Tail Recursion: is a specific type of recursion where the recursive call is the last statement within the function. Head Recursion: Is a specific type of recursion where the recursive call is the first statement within the function. 13

14. Tail Recursion: 14

15. Head Recursion: 15

16. Advantages of Recursion : Recursion is very simple and easy to understand. It requires a minimal number of programming statements. Recursion will break the problem into smaller pieces of sub problems for example Square root. It is used to solve mathematical, trigonometric, or any type of algebraic problems. It is useful in solving data structure problems like linked lists, queues and stacks. Complex tasks can be solved easily. 16

17. Disadvantages of Recursion : It consumes more storage space than other techniques such as iteration (loops), Dynamic programming etc. If base condition is not set properly then it may create a problem such as a system crash, freezing etc., Compared to other techniques recursion is a time-consuming process and less efficient. It is difficult to trace the logic of the function. Computer memory is exhausted if recursion enters an infinite loop. Excessive function calls are being used. Each function called will occupy memory in stack. Which will lead to stack overflow. 17

18. Recursive Algorithms Here are some specific examples of Recursive Algorithms: Factorial Calculation Fibonacci Sequence Binary Search Tower of Hanoi 18

19. Factorial Calculation The factorial of a non-negative integer n is the product of all positive integers less than or equal to n. Recursive Formula: Base Case: factorial(0) = 1 Recursive Case: factorial(n) = n * factorial(n-1 ) 19

20. Fibonacci Sequence A sequence of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... Recursive Implementation: Base Cases: fibonacci(0) = 0 fibonacci(1) = 1 Recursive Case: fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2) The function calls itself with smaller values until it reaches the base cases. 20

21. Binary Search Binary search is an efficient algorithm for finding an item from a sorted list of items. Base Case: If the lower bound becomes greater than the upper bound (meaning the search space is empty), the element is not found (return -1 or some appropriate value). If the target element is found at the middle index (comparison with the middle element), return the middle index (element found!). Recursive Case: Calculate the middle index of the current search space. Compare the target element with the element at the middle index: If the target element is less than the middle element, recursively call the function with the left half of the search space (update upper bound to middle index - 1). If the target element is greater than the middle element, recursively call the function with the right half of the search space (update lower bound to middle index + 1). 21

22. Tower of Hanoi The Tower of Hanoi is a classic problem involving moving disks from one peg to another, following specific rules. Problem Description: Base Case: Move a single disk directly to the destination. Recursive Case: Move n-1 disks from source to auxiliary peg. Move the nth disk from source to destination peg. Move the n-1 disks from auxiliary peg to destination peg. 22 Tower of Hanoi puzzle with n disks can be solved in minimum 2 n −1 steps. This presentation shows that a puzzle with 3 disks has taken 2 3  - 1 = 7 steps.

23. Recursion in Data Structure Recursion is particularly powerful when working with certain data structures, such as trees and linked lists, because these structures are inherently recursive. So here are examples of recursion in data structure: Recursion in Arrays Recursion in Linked Lists 23

24. Recursion in LinkedList A linear data structure where each element (node) points to the next node. Components : Node : Contains data and a reference to the next node . Head : The first node in the list. 24

25. Recursive Operation on Linked Lists 25 Finding the Length of a Linked List: Iteratively, we would use a counter and iterate through the list until we hit a null pointer. Recursively, we can: Base Case: If the list is empty (head is null), return 0 (length is 0). Recursive Case: Call the function recursively on the next node. Processing: Add 1 to the result of the recursive call (length of the remaining list).

26. Recursion in Array An array is a collection of elements identified by index or key. Characteristics : Fixed size. Elements are of the same data type. Indexed from 0 to n-1. 26

27. Recursive Operation on Array 27 Reversing an Array: The recursive approach to reversing an array involves swapping elements from the beginning and end of the array and then recursively processing the sub-array that excludes these elements. Base Case: The base case occurs when the start index is greater than or equal to the end index, meaning that the entire array (or sub-array) has been processed. Recursive Case: Swap the elements at the start and end indices, then recursively call the function with the next indices.

28. Time and Space Complexity in Recursion Time Complexity: Time complexity refers to the amount of time an algorithm takes to execute as the input size increases. In recursion, time complexity is often analysed based on the number of function calls made. A common case is linear time complexity (O(n)), where the number of calls grows proportionally with the input size (n). For example, a recursive function that iterates through an array will have linear time complexity. 28

29. Example - Factorial Calculation Time Complexity Analysis: Function Calls: For factorial(n), there are n recursive calls. Time Complexity: O(n), as each call performs a constant amount of work. 29

30. Example - Fibonacci Sequence Time Complexity Analysis: Function Calls: The number of calls grows exponentially due to repeated calculations. Time Complexity: O(2^n), as each call generates two more calls except for base cases . 30

31. Time and Space Complexity in Recursion Space Complexity: Space complexity refers to the amount of memory an algorithm uses during execution. In recursion, space complexity is often determined by the depth of the recursion tree, which represents the chain of function calls. Each recursive call adds a frame to the call stack, which consumes memory. A function with constant space complexity per call (O(1)) and a recursion depth of n will have a space complexity of O(n). 31

32. Example – Factorial Calculation (Space) Space Complexity Analysis: Stack Depth: For factorial(n), the stack depth is n. Space Complexity: O(n), as each call waits for the result of the next call. 32

33. Example - Fibonacci Sequence (Space) Space Complexity Analysis: Stack Depth: For fib_recursive(n), the stack depth is n. Space Complexity : O(n), as each call waits for the result of the next calls. 33

34. Conclusion Recursion is a powerful technique for simplifying complex problems in data structures. With proper understanding and application, it enables us to solve problems more elegantly and efficiently. Let's embrace recursion as a valuable tool in our programming journey! 34

35. Thank you Basit Ali Somoro (CSC-23S-239 ) Khuda Bux Magsi (CSC-23F-259)

36. Any Question Feel free to ask…