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

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