Recursion & Search Lecture PDF

Recursion & Search Prepared By: Dr. Asmaa Awad  Factorial Factorial (5)=5*4*3*2*1=120  O(n) 2  Factorial Factorial (5)=5*4*3*2*1=120  O(n) OR Recur...

Recursion & Search Prepared By: Dr. Asmaa Awad  Factorial Factorial (5)=5*4*3*2*1=120  O(n) 2  Factorial Factorial (5)=5*4*3*2*1=120  O(n) OR Recursion 3  Content What is Recursion? Why Recursion Recursion Function Example Recursion & Iterative Using Recursion in Binary Search 4  Recursion Recursion: A technique for solving a large computational problem by repeatedly applying the same procedure to reduce it to successively smaller problems. Recursion: Recursion refers to a programming technique in which a function calls itself either directly or indirectly. Recursion: Recursion is a common mathematical and programming concept. 5  Recursion Definition: Recursion is a process in which a function calls itself directly or indirectly. Key Concept: Each recursive function has two main parts:  Base Case: Stops the recursion when a specific condition is met.  Recursive Case: The function calls itself with modified parameters to approach the base case. Note: Without a base case, a recursive function will result in infinite recursion. 6  Why learn recursion? "cultural experience" - A different way of thinking of problems Can solve some kinds of problems better than iteration Leads to elegant, simplistic, short code (when used well) Many programming languages ("functional" languages such as Scheme, ML, and Haskell) use recursion exclusively (no loops) 7  The idea Recursion is all about breaking a big problem into smaller occurrences of that same problem. – Each person can solve a small part of the problem. What is a small version of the problem that would be easy to answer? What information from a neighbor might help me? 8  Recursive algorithm Number of people behind me: – If there is someone behind me, ask him/her how many people are behind him/her. When they respond with a value N, then I will answer N + 1. – If there is nobody behind me, I will answer 0. 9  How Recursive Works Overview of how recursive function works: Recursive function is called by some external code. If the base condition is met then the program do something meaningful and exits. Otherwise, function does some required processing and then call itself to continue recursion. Here is an example of recursive function used to calculate factorial. Example: Factorial is denoted by number followed by (!) sign i.e 5! Steps: 10  Recursive Function Example O(N) 11  Fibonacci Function 0 1 1 2 3 5 8 12 12  Fibonacci Function Writing a Recursive Function: The Fibonacci numbers are easy to write as a Python function. It’s more or less a one to one mapping from the mathematical definition: 13 Fibonacci Function 14 Searching Algorithm s in Python 15  Searching Algorithms Searching is an operation or a technique that helps find the place of a given element or value in the list. Any search is said to be successful or unsuccessful depending upon whether the element that is being searched is found or not. Searching Algorithms  Linear Search.  Binary Search. 16  Linear search Linear search is the simplest searching algorithm. It sequentially checks each element of the list until it finds the target value. Steps: Start from the first element of the list. Compare each element of the list with the target value. If the element matches the target value, return its index. If the target value is not found after iterating through the entire list, return -1. 17 Linear Search O(n) 18 Binary Search 19 Binary Search 20 Binary Search 21 Binary Search 22  Binary Search Binary search is a more efficient searching algorithm suitable for sorted lists. It repeatedly divides the search interval in half until the target value is found. Steps: 1.Start with the entire sorted list. 2.Compute the middle element of the list. 3.If the middle element is equal to the target value, return its index. 4.If the middle element is less than the target value, search in the right half of the list. 5.If the middle element is greater than the target value, search in the left half of the list. 6.Repeat steps 2-5 until the target value is found or the search interval is empty. 23 Binary Search O(log(n)) 24 Binary Search O(log(n)) 25  Binary Search Advantages of Binary Search  Binary search is faster than linear search, especially for large arrays.  More efficient than other searching algorithms with a similar time complexity, such as interpolation search or exponential search.  Binary search is well-suited for searching large datasets that are stored in external memory, such as on a hard drive or in the cloud. Disadvantages of Binary Search  The array should be sorted.  Binary search requires that the data structure being searched be stored in contiguous memory locations.  Binary search requires that the elements of the array be comparable, meaning that they must be able to be ordered. 26