Recursion¶
Quick Start Guide¶
stack
:- Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
A stack allows access to only one data item: the last item inserted. If you remove this item, you can access the next-to-last item inserted, and so on.
A stack is also a handy aid for algorithms applied to certain complex data structures. In “Binary Trees”, we’ll see it used to help traverse the nodes of a tree.
Notice how the order of the data is reversed. Because the last item pushed is the first one popped.
commonly implemented with linked lists but can be made from arrays too.
operations of stack: pop(), push(), tos(), isEmpty(), display().
Recursion Programs¶
Author : Robin Singh
Programs List : 1 . Factorial 2 . Fibonacci 3 . Tower Of Hanoi 4 . Binary Search (Recursive)
- pythorn.data_structures.recursion.tower_of_hanoi(disk, source, destination, auxiliary)[source]¶
Tower Of Hanoi Implementation Using Recursion
Tower of hanoi is a mathematical puzzle.It consists of three poles and a number of disks of different sizes which can slide onto any poles.
The puzzle starts with a disk in a neat stack u ascending order of size in one pole, the smallest at the top making it a conical shape.
The objective of the puzzle is to move all the disks from one pole (Source Pole) to another pole (Destination pole) with the help of the third pole (auxiliary pole)
The puzzle has two rules : 1 . You Can’t place a larger disk onto smaller disk or vice-versa 2 . Only one disk can be moved at a time
Moves Reqd to Solve This puzzle is given by : 2^(n)-1
Example : Number Of Dics : 3 Source Pole : A Destination Pole : C Auxiliary Pole : D
Solution : Tower_of_hanoi(3,”A”,”B”,”C”) Move Disk From Source A To Destination B Move Disk From Source A To Destination C Move Disk From Source B To Destination C Move Disk From Source A To Destination B Move Disk From Source C To Destination A Move Disk From Source C To Destination B Move Disk From Source A To Destination B
- pythorn.data_structures.recursion.binary_search(A, key, low, high)[source]¶
Implementation of Binary Search Recursive Method
Below function perform sa binary search on a sorted list and returns the index of the item if it;s present else returns false
- param list
a sorted list
- param key
key to search from given sorted list
- return
index of key if its found in the sorted list else returns false
Example : A = [5 9 10 45 65 78 98 102 1045] Key = 11
Binary_Search(A,11,0,len(A))
Solution : Not Present
A = [5 9 10 45 65 78 98 102 1045] Key = 65
Binary_Search(A,65,0,len(A))
Solution :
Element is Present at index : 4