UNIT1 data structure recursion model with example.pptx

This explains about the data structure recursion

1. Recursion Recursion is a technique by which a function makes one or more calls to itself during execution. recursion provides an elegant and powerful alternative for performing repetitive tasks. Recursion can be used to solve some interesting problems easily, such as Towers of Hanoi, Tree Traversals, etc.

2. Illustrative Examples: Recursion is an important technique in the study of data structures and algorithms. Below are the four illustrative examples of the use of recursion: • The factorial function (commonly denoted as n !) is a classic mathematical function that has a natural recursive definition. • An English ruler has a recursive pattern that is a simple example of a fractal structure. • Binary search is among the most important computer algorithms. It allows us to efficiently locate a desired value in a data set with upwards of billions of entries. • The file system for a computer has a recursive structure in which directories can be nested arbitrarily deeply within other directories. Recursive algorithms are widely used to explore and manage these file systems.

3. The Factorial Function The factorial of a positive integer n , denoted n !, is defined as the product of the integers from 1 to n . If n = 0, then n ! is defined as 1 by convention. More formally, for any integer n ≥

4. A Recursive Implementation of the Factorial Function 1 def factorial(n): 2 if n == 0: 3 return 1 4 else: 5 return n * factorial(n−1)

5. A recursion trace for the call factorial A recursion trace closely mirrors the programming language’s execution of the recursion .

6. Drawing an English Ruler As a more complex example of the use of recursion, consider how to draw the markings of a typical English ruler. For each inch, we place a tick with a numeric label. We denote the length of the tick designating a whole inch as the major tick length . Between the marks for whole inches , the ruler contains a series of minor ticks , placed at intervals of 1/2 inch, 1/4 inch, and so on. As the size of the interval decreases by half, the tick length decreases by one.

7. A 3-inch ruler with major tick length 3 The English ruler pattern is a simple example of a fractal , that is, a shape that has a self-recursive structure at various levels of magnification.

8. Illustrating Ruler Drawing Using a Recursion Trace

9. Recursive Approach to Ruler Drawing In general, an interval with a central tick length L ≥ 1 is composed of: • An interval with a central tick length L −1 • A single tick of length L • An interval with a central tick length L −1

10. Python code to draw an English Ruler class EnglishRuler : def __init__(self, num_inches , major_length ): self.__num_inches = num_inches self.__major_length = major_length def draw_line ( self,tick_length,tick_label =''): line = '-' * tick_length if tick_label : line += '' + tick_label print(line) def draw_interval (self, center_length ): if center_length > 0: self.draw_interval (center_length-1) self.draw_line ( center_length ) self.draw_interval (center_length-1) def draw_ruler (self): self.draw_line (self.__major_length,'0') for j in range(1, 1+self.__num_inches): self.draw_interval (self.__major_length-1) self.draw_line ( self.__major_length,str (j)) if __name__ == '__main__': ruler = EnglishRuler (5,4) ruler.draw_ruler ()

11. Binary Search Binary search is a divide-and-conquer algorithm that can be used to find the position of a target value within a sorted array. The algorithm works by repeatedly dividing the search interval in half until the target value is found or the search interval is empty. Binary search is a very efficient algorithm, and it is often used in real-world applications such as searching for a word in a dictionary or finding a customer record in a database.

12. 1 def binary search(data, target, low, high): 2 ”””Return True if target is found in indicated portion of a Python list. 3 4 The search only considers the portion from data[low] to data[high] inclusive. 5 ””” 6 if low > high: 7 return False # interval is empty; no match 8 else: 9 mid = (low + high) // 2 10 if target == data[mid]: # found a match 11 return True 12 elif target < data[mid]: 13 # recur on the portion left of the middle 14 return binary search(data, target, low, mid − 1) 15 else: 16 # recur on the portion right of the middle 17 return binary search(data, target, mid + 1, high)

13. File Systems Modern operating systems define file-system directories (which are also sometimes called “folders”) in a recursive way. Namely, a file system consists of a top-level directory, and the contents of this directory consists of files and other directories, which in turn can contain files and other directories, and so on. The operating system allows directories to be nested arbitrarily deep (as long as there is enough space in memory), although there must necessarily be some base directories that contain only files, not further subdirectories.

14. A portion of a file system demonstrating a nested organization as below:

15. Computing the total disk usage for all files and directories nested within a particular directory. In below example, the cs016 directory uses only 2K of immediate space, but a total of 249K of cumulative space. The cumulative disk space for an entry can be computed with a simple recursive algorithm. It is equal to the immediate disk space used by the entry plus the sum of the cumulative disk space usage of any entries that are stored directly within the entry.

16. A recursive function for reporting disk usage of a file system 1 import os 2 3 def disk usage(path): ”””Return the number of bytes used by a file/folder and any descendents.””” 5 total = os.path.getsize (path) # account for direct usage 6 if os.path.isdir (path): # if this is a directory, 7 for filename in os.listdir (path): # then for each child: 8 childpath = os.path.join (path, filename) # compose full path to child 9 total += disk usage( childpath ) # add child’s usage to total 10 11 print ( {0:<7} .format(total), path) # descriptive output (optional) 12 return total # return the grand total

17. Array based sequences: A n array is a data structure that stores a collection of elements of the same data type. Arrays are typically implemented as contiguous blocks of memory, which makes them efficient for accessing elements in random order. There are two main types of arrays: low-level arrays and dynamic arrays . Low-level arrays are arrays in which the size of the array is fixed at compile time. This means that the programmer must specify the number of elements that the array will hold when it is created . Low-level arrays can be efficient for some applications, but they can be inflexible and difficult to use.

18. Array based sequences: Dynamic arrays, on the other hand, are arrays in which the size of the array can be changed at runtime. This makes dynamic arrays more flexible and easier to use than low-level arrays. However, dynamic arrays can be less efficient than low-level arrays, because the size of the array must be changed dynamically .

19. A rray in low level The primary memory of a computer is composed of bits of information and those bits are typically grouped into larger units that depend upon the precise system architecture. Such a typical unit is a byte, which is equivalent to 8 bits .

20. A computer system will have a huge number of bytes and memory and to keep track of what information is stored and what byte the computer uses in abstraction known as a memory address and in effect each byte of memory is associated with a unique number that serves as its address . any byte of the main memory can be efficiently accessed based upon its memory address in this sense we can say that a computer’s main memory performs as a random-access memory. So, each individual byte of memory can be stored or retrieved in order one-time O(1).

21. Advantages of Dynamic Arrays Dynamic arrays have several advantages over low-level arrays, including : Flexibility: Dynamic arrays can be resized at runtime, which makes them more flexible and easier to use than low-level arrays. Efficiency: Dynamic arrays can be efficient for some applications, but they can be less efficient than low-level arrays, because the size of the array must be changed dynamically. Memory usage: Dynamic arrays can use less memory than low-level arrays, because they can be resized to fit the amount of data that is actually needed.

22. Disadvantages of Dynamic Arrays Dynamic arrays also have some disadvantages, including : Complexity : Dynamic arrays can be more complex to implement than low-level arrays . Performance : Dynamic arrays can be less efficient than low-level arrays, because the size of the array must be changed dynamically.

23. Applications of Dynamic Arrays Lists: Dynamic arrays are often used to implement lists, which are a common data structure in programming . Stacks : Dynamic arrays are often used to implement stacks, which are a data structure that stores data in a last-in-first-out (LIFO) order . Queues: Dynamic arrays are often used to implement queues, which are a data structure that stores data in a first-in-first-out (FIFO) order. Trees: Dynamic arrays can be used to implement trees, which are a data structure that stores data in a hierarchical order. Graphs: Dynamic arrays can be used to implement graphs, which are a data structure that stores data in a network of nodes and edges .

24. Dynamic Array in Python A dynamic array is similar to an array, but the difference is that its size can be dynamically modified at runtime. The programmer doesn’t need to specify how large an array will be, beforehand. class DynamicArray :     def __init__(self):         self.array = []     def append(self, item):         self.array.append (item)     def get(self, index):         return self.array [index]     def size(self):         return len ( self.array ) my_array = DynamicArray () my_array.append (11) my_array.append (12) my_array.append (13) print(my_array.get(0))   print(my_array.get(1))   print(my_array.get(2))   size = my_array.size () print( f"Total Array Size={size}")

25. Priority Queues A priority queue is a type of queue that organizes elements based on their priority values. Elements with higher priority values are usually retrieved before elements with lower priority values. We define the priority queue ADT to support the following methods for a priority queue P: P.add (k, v): Insert an item with key k and value v into priority queue P. P.min( ): Return a tuple , ( k,v ), representing the key and value of an item in priority queue P with minimum key (but do not rexmove the item); an error occurs if the priority queue is empty. P.remove min( ): Remove an item with minimum key from priority queue P, and return a tuple , ( k,v ), representing the key and value of the removed item; an error occurs if the priority queue is empty. P.is empty( ): Return True if priority queue P does not contain any items. len (P): Return the number of items in priority queue P.

26. The relational property is the following: Heap-Order Property: In a heap T, for every position p other than the root, the key stored at p is greater than or equal to the key stored at p’s parent. Complete Binary Tree Property: A heap T with height h is a complete binary tree if levels 0,1,2,...,h− 1 of T have the maximum number of nodes possible (namely, level i has 2i nodes, for 0 ≤ i ≤ h− 1) and the remaining nodes at level h reside in the leftmost possible positions at that level.

27. Implementing a Priority Queue with a Heap Adding an Item to the Heap: To maintain the complete binary tree property, that new node should be placed at a position p just beyond the rightmost node at the bottom level of the tree, or as the leftmost position of a new level, if the bottom level is already full (or if the heap is empty).

28. Up-Heap Bubbling After an Insertion:

29. Removing the Item with Minimum Key We know that an entry with the smallest key is stored at the root r of T. We cannot simply delete node r, because this would leave two disconnected subtrees . Instead, we ensure that the shape of the heap respects the complete binary tree property

30. Sorting with a Priority Queue