Recursion is the ability for a function to call itself. Many problems are more easily solvable using recursion. Using recursion may place a greater burden on the amount of memory the program uses. A recursive function must have a stop condition otherwise the program may keep running forever. Recursion programs may be more difficult to follow through because we are not used to keeping track of things that flow in such a manner.
File: "intro1.py"
def function1( number1 ) :
if number1 == 1 :
print( number1 )
return
else :
function1( number1 - 1 )
print( number1 )
function1( 1 )
print( "-------------" )
function1( 2 )
print( "-------------" )
function1( 3 )
Output:
1
-------------
1
2
-------------
1
2
3
Explain the function below and it's output.
File: "intro2.py"
def function1( number1 ) :
print( number1 )
if number1 == 1 :
return
else :
function1( number1 - 1 )
function1( 1 )
print( "-------------" )
function1( 2 )
print( "-------------" )
function1( 3 )
Output:
1
-------------
2
1
-------------
3
2
1
File: "list1.py"
def mysum(L):
if not L:
return 0
else:
return L[0] + mysum(L[1:])
list1 = [ 4 ,5 , 6 ]
print( mysum( list1 ) )
Output:
15
Let us study a little bit more complicated form of list. This list can contain other nested lists of different levels with numbers being the items in the list. Our problem is to sum all the numbers in the list. There is no limit to the number of nested levels.
list1 = [ [1,2] , [3.4] ]
list1 = = [ 1, [3, 4] , 6 ]
list1 = [ [ [1,2] , 3 ] , 5 ]
If we try to solve this problem with loops we realize that we cannot come up with a solution.
Recursive Solution
File: "sumtree1.py"
def sumtree(L):
tot = 0
print( "L:" , L )
for x in L: # For each item at this level
if not isinstance(x, list):
tot += x # Add numbers directly
print( "Adding x to total" )
else:
print( "Total:" , tot )
tot += sumtree(x) # Recur for sublists
return tot
Let us see how the above behaves for :
list1 = [ [1,2] , [3.4] ]
for x in L gives us [1,2] and [3,4]
Since x is a list we go to the "else" part and do :
tot += sumtree( [1,2] ;
Now this goes to
for x in [1,2]
Now we go to if part and "tot" is equal to 3
Now we go to the next element [3,4]
Calling "sumtree" on that will give us 7 .
So now the tot is 10 and we come out of the original
"for x in L:"
with the total value as 10 .
Writing the above in an iterative form is not easy. Problems like the above can be rewritten with a trick ( utilizing a structure called a stack ) .
def nested_sum(seq):
stack = []
stack.append(seq)
result = 0
while stack:
item = stack.pop()
print( "Item popped." , item )
if isinstance(item, list):
for e in item:
stack.append(e)
else:
result += item
return result
Let us see how the above algorithm works for :
list1 = [ [1,2] , [3.4] ]
stack gets appended the whole "list1" . We pop the list and since each item is a list the stack now contains:
stack = [1,2] [3,4]
We go in the while loop and pop the [3,4] and since it is a list we append to the stack.
stack = [1,2] , 3, 4
We now pop 4 and since it is not a list we add it to the result.
result = 4
We then enter the while loop and pop 3 and add 3 to result to give it 7 . We then pop [1,2] and since it is a list
we add the elements to the stack.
stack = 1 , 2
We then will pop 2 and add it to result and same for 1 and make the whole thing 7 .
Example :
Write a program to validate the grammar of the string with matching parentheses.
Valid cases:
"{ { } } " , " { } { } { { { } } }"
Invalid Cases:
"{ } } " , "{ " , " }} "
We are going to use a list as a stack.
File: "grammar1.py"
def checkGrammar ( str1 ) :
stack1 = []
beginCh = "{"
endCh = "}"
for x1 in str1 :
if x1 == beginCh :
stack1.append ( beginCh )
else:
if ( len( stack1 ) == 0 ) :
return False
else :
stack1.pop()
if len( stack1 ) == 0 :
return True
else :
return False
print( checkGrammar( "{}" ) )
print( checkGrammar( "{{}" ) )
print( checkGrammar( "{}{{}}" ) )
print( checkGrammar( "}}" ) )
print( checkGrammar( "{{{}}}{{}}" ) )
Output:
True
False
True
False
True
1)
Find the modulus of a number by a divisor .
File: "mod2.py"
def findMod( number1, divisor ) :
if( number1 < divisor ) :
return number1
else:
return ( findMod( number1-divisor ,divisor ) )
print( findMod( 9 , 5 ) )
print( findMod( 15 , 4 ) )
2)
Find if a string is a palindrome.
def isPalin( str1 ) :
if ( len( str1 ) > 1 ) :
l1 = len( str1 )
if ( str1[0] != str1[ l1-1 ] ) :
return False
else :
str1 = str1[1 : l1-1 ]
print( "len:" , len( str1 ) )
return isPalin( str1 )
return True
str1 = "cat"
str1 = "bbcacbb"
str1 = "bbdacbb"
str1 = "bbcb"
str1 = "cbabc"
str1 = "ctadc"
print( isPalin( str1 ) )
3)
Find out if a number is prime.
File: prime1.py"
def findPrime( number1, divisor ) :
if( number1 % divisor == 0 ) :
return False
if ( divisor* divisor > number1 ):
return True
return ( findPrime( number1 , divisor+1 ) )
print( findPrime( 9 , 2 ) )
print( findPrime( 15 , 2 ) )
print( findPrime( 7 , 2 ) )
Hanoi Towers
https://www.geeksforgeeks.org/c-program-for-tower-of-hanoi/
File: "hanoi1.py"
def moveTower( height,fromPole, toPole, withPole ):
if height >= 1:
moveTower( height-1,fromPole, withPole, toPole )
moveDisk( height , fromPole, toPole )
moveTower( height-1, withPole, toPole, fromPole )
def moveDisk( diskNo, fp,tp):
print("moving disk", diskNo , "from",fp,"to",tp)
print( "A is the source." )
print( "B is the des." )
print( "C is the spare." )
print() ; print()
moveTower(3,"A","B","C")
#Do cases of 1 , 2 ,3 and 4
Powers of 2
1)
#Write the code for the below function
# recursively so that it returns the power of 2
# power2( 3 ) returns 8
# power2( 1 ) returns 2
# power2( 2 ) returns 4
def power2( number1 ) :
print( power2( 1 ) )
print( power2( 2 ) )
print( power2( 3 ) )
Output:
2
4
8
2)
Factorial of a number is defined as the product of all the numbers below it.
factorial ( 2 ) = 2 * 1 = 2
factorial ( 4 ) = 4 * 3 * 2 * 1 = 24
#Write the code for the below function
def factorial( number1 ) :
print( factorial( 1 ) )
print( factorial( 2 ) )
print( factorial( 3 ) )
3)
A fibonacci sequence is defined as the sum of it's previous 2 numbers with the initial numbers being 1 and 1 .
1, 1, 2 , 3 , 5, 8 , 13 , 21
#Write a recursive function
def FibonacciRecursive( number1 ) :
def FibonacciGen( limit1 ) :
fib1 = 1
fib2 = 2
print( FibonacciRecursive(6 ) )
Expected Output:
8
1)
#Write the code for the below function
# recursively so that it returns the power of 2
# power2( 3 ) returns 8
# power2( 1 ) returns 2
# power2( 2 ) returns 4
def power2( number1 ) :
print( power2( 1 ) )
print( power2( 2 ) )
print( power2( 3 ) )
2)
#Write the code for the below function
def factorial( number1 ) :
if number1 == 1 :
return 1
return ( number1 * factorial( number1-1 ) )
print( factorial( 1 ) )
print( factorial( 2 ) )
print( factorial( 3 ) )
3)
#Write a recursive function
def FibonacciRecursive( number1 ) :
if number1 == 1 or number1 == 2 :
return 1
return ( FibonacciRecursive( number1-1 ) +
FibonacciRecursive( number1-2 ) )
print( FibonacciRecursive(6 ) )