Python - Recursion





Recursion allows a function to call itself. Fixed steps of code get executed again and again for new values. We also have to set criteria for deciding when the recursive call ends. In the below example we see a recursive approach to the binary search. We take a sorted list and give its index range as input to the recursive function.

Binary Search using Recursion

We implement the algorithm of binary search using python as shown below. We use an ordered list of items and design a recursive function to take in the list alogn with starting and ending index as input. Then the binary search function calls itself till find the the searched item or concludes about its absence in the list.

def bsearch(list, idx0, idxn, val):

    if (idxn < idx0):
        return None
    else:
        midval = idx0 + ((idxn - idx0) // 2)
# Compare the search item with middle most value

        if list[midval] > val:
            return bsearch(list, idx0, midval-1,val)
        elif list[midval] < val:
            return bsearch(list, midval+1, idxn, val)
        else:
            return midval

list = [8,11,24,56,88,131]
print(bsearch(list, 0, 5, 24))
print(bsearch(list, 0, 5, 51))

When the above code is executed, it produces the following result −

2
None


Frequently Asked Questions

+
Ans: Python Data Structure Introduction - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..
+
Ans: Python Data Structure Introduction - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..
+
Ans: Python Data Structure Introduction - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..
+
Ans: Python Data Structure Introduction - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..
+
Ans: Python Data Structure Introduction - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..
+
Ans: Python Data Structure Introduction - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..
+
Ans: Python Data Structure Introduction - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..
+
Ans: Python Data Structure Introduction - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..
+
Ans: Python Data Structure Introduction - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..
+
Ans: Python Data Structure Introduction - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..
+
Ans: Python Data Structure Introduction - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..
+
Ans: Python Data Structure Algorithm Classes - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..
+
Ans: Python Data Structure Introduction - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..
+
Ans: Python Data Structure Introduction - Learn Python Data Structure in simple and easy steps starting from basic to advanced concepts with examples including Introduction, Environment, Arrays, Lists, Tuples, Dictionary, 2-D Array, Matrix, Sets, Maps, Linked Lists, Stack, Queue, Dequeue, Advanced Linked list, Hash Table, Binary Tree, Search Tree, Heaps, Graphs, Algorithm Design, Divide and conquer, Recursion, backtracking, Tree Traversal, Sorting, Searching, Graph Algorithms, Algorithm Analysis, Big-O Notation, Algorithim classes, Amortized analysis, Algorithm Justifications. view more..
+
Ans: Python Network Programming - Learn Python Network Programming in simple and easy steps starting from basic to advanced concepts with examples. view more..
+
Ans: Python Network Programming Introduction - Learn Python Network Programming in simple and easy steps starting from basic to advanced concepts with examples. view more..
+
Ans: Python Netwrok Environment - Learn Python Network Programming in simple and easy steps starting from basic to advanced concepts with examples. view more..
+
Ans: Python Internet Protocol - Learn Python Network Programming in simple and easy steps starting from basic to advanced concepts with examples. view more..




Rating - NAN/5
526 views

Advertisements