# Recursion in Python Class 12 CS Solutions

Recursion in Python Solutions for CBSE Computer Class 12. Solved assignment of Computer Science conceptual, application and programing questions of Sumita Arora Class XII book as per NCERT Syllabus. Question answers are very useful for half yearly and board examination.

### Conceptual Questions

Q.1. What is a recursive function? Write one advantage of recursive functions.

Recursive functions are function that call itself. Advantage of recursive functions is it reduces time complexity for some programs.

Q.2. What is direct recursion and indirect recursion ?

Direct recursion occur when a function call itself.
Indirect recursion occurs when a function calls another function and this function calls the first function. It means it is indirectly called by another function through the first function.

Q.3.What are the two cases required in a recursive function?

Base case it is last recursive step after this no recursive function calling is done when the base case is reached .
Recursive case the function call itself recursively

Q.4.What is base case?

Base case it is last recursive step after this no recursive function calling is done when the base case is reached.

Q.5.What is recursive case?

Recursive case the function call itself recursively.

Q.6.Is it necessary to have a base case in a recursive function? why/why not?

Yes , it is necessary to have a base case. If there is no base case the functions runs on infinte time. It will terminate with an error.

Q.7.What is infinite recursion ? why does it occur?

Infinite recursion – When the function goes on calling itself infinitely , means there is no base case then the infinite recursion occur.

Q.8.How can you stop/resolve an infinite recursion?

Base case it is last recursive step after this no recursive function calling is done when the base case is reached.

`Q.9.Give some examples that can be represented recursively.`
```Answer:
i)Sum of 1 to n
i=0
def func(n,s=0):             #Sum of 1 to n
if n==0:
return s
s +=n
return func(n-1,s)
#print(i)

ii)factorial
i=0
def fact(n):         #factorial
if n<=1:
return 1
return n*fact(n-1)
#print(i)
print(fact(6))```
`Q.10.Can each recursive function be represented through iteration? Give examples.`
```Answer:
i)#recursive
Sum of 1 to n
i=0
def func(n,s=0):
if n==0:
return s
s +=n
return func(n-1,s)
#print(i)
#iterative
def func(n):
s=0
for i in range (1,n+1):
s+=i
return s

ii)
#recursive
#factorial
i=0
def fact(n):
if n<=1:
return 1
return n*fact(n-1)#recursion
#print(i)
print(fact(6))

#iterative
i=0
def fact(n):
f=1
for i in range( 1,n+1):
f=f*i
return f
#print(i)```

Q.11.Which of the functions given in previous question will result into infinite recursion?

``` Answer:
#factorial
def fact(n):# base case to be removed for making this program infinite loop
if n<=1:
return 1
return n*fact(n-1)
i=0
print(fact(6))
#factorial infinite loop as i remove the base case.
def fact(n):
return n*fact(n-1)
#print (i)
print(fact(6)) ```
```Q.12.Identify the base case in the following recursive function:
def function1(n):
if n==0:
return 5
elif n==1:
return 8
elif n>0:
return function1(n-1)+function1(n-2)
else:
return -1 ```

function1(0)=5
function1(1)=8
are base cases.

Q.13.Why are recursive functions considered slower than their iterative counterparts?

It is because of extra stack manipulation, recursive versions of functions often run slower and use more memory than their iterative counterparts.

Q.14.If any recursive function can be easily written using iterative code, then what is the need for recursion? When would you prefer recursion over iteration and vice versa?

It simplifies Problem. It make solution look shorter. It depends on the program which one is to be used for which problem example :’Tower of Hanoi’.

Q.15.Compare and contrast the use of iteration and recursion in terms of memory space and speed.

It is slower , high RAM is used , More memory spaces is used. They are used because sometime they greatly simplifies the problem.

### Application Based Questions : Recursion in Python Class 12

Q1. Consider square numbers defined as follows:
compute(1) = 1
compute(N) = compute(N-1) + 2N – 1
According to this definition, what is compute(3) ?

(a) compute(3) = compute(2) + compute(1)
(b) compute(3) = compute(2) – 2*3 +1
(c) compute(3) = compute(2) +2*3 -1
(d) compute(3) = compute(3) +2*3-1

Option (c) is correct.

```Q2. Look at compute numbers again:
compute (1) = 1
compute (N) = compute (N-1) + 2N-1
Which Python function below successfully implements this definition?
(a)
def compute(N):
if N<1:
return 1
else:
return N. N
(b)
def compute(N) :
if N ==1:
return 1
else:
return compute(N-1) + 2 *N – 1
(c)
def compute(N) :
if N = 1:
return 1
else:
return compute(N-1) + 2 *N – 1
(d)
def compute(N) :
if N = 1:
return 1
else:
return compute(N)```

Option (b) is successfully implements this definition.

```Q9. Figure out the problem with following code that may occur when it is run?
def recur(p) :
if p == 0:
print("##")
else:
recur(p)
p=p-1
recur(5)```
```Answer :
indentation
def recur(p) :
if p == 0:
print (“##”)
else:
return recur(p-1)
recur(5)```

Q.10. Check point 6.1 has some recursive functions that cause infinite recursion. Make changes in the definition of those recursive functions so that they recur finitely and produce a proper output.

```Answer:
# Checkpoint 6.1
(b)
def recur(p):
if p == 0:
print(“##”)
else:
recur(p)
p = p-1
recur(5)
# The above code will run into infinite recursion because the value of p is being decremented after the recursion call. So it is never actually changing. The correct way:
def recur(p):
if p == 0:
print(“##”)
else:
p = p-1
recur(p)
recur(5)
(d)
def Check(c) :
Mate(c+1)
def Mate(d) :
Check(d-1)
# The above code has no base case and will run into infinite recursion. It can be corrected as following
def Check(c):
if c > 10: # Any base case can be added
return
else:
c = c+1 # Increment is important
Mate(c+1)
def Mate(d) :
Check(d-1)```

### Programming practice/Knowledge based question

Q.1.Write a function that takes a number and tests if it is a prime number using recursion technique.

```Answer:
i=0
count = 0
def prime(num,n) : #takes a number and tests if it is a prime number
if n == num :
return num
else :
global count
if num % n == 0 :
count  += 1
prime(num , n+1)

#print(i)
num = int(input("Enter a number : "))
prime( num , 2 ) #using recursion technique.

if count > 0 :
print(num, "is not prime number")
else :
print(num , "is Prime number ")```

Q.2. Implement a function product() to multiply 2 numbers recursively using + and – operators only.

```Answer:
i=0
def product( num1 , num2 ): #function product() to multiply 2 numbers recursively
if 0 == num2 :
return 0
else :
return product(num1 , num2 - 1 ) + num1

a = int(input("Enter a number : "))
b = int(input("Enter second number :"))
print(product( a , b))
#print(i)```

Q.3. The hailstone sequence starting at a positive integer n is generated by following two simple rules. If n even, the next number in the sequence is n/ 2. If n is odd, the next number in the sequence is 3*n+1 Repeating this process, the hailstone sequence gets generated. Write a recursive function hailstone ( n) Which prints the hailstone sequence beginning at 1. Stop when the sequence reaches the number 1 (since otherwise, we would loop forever 1, 4, 2, 1, 4, 2, ….).

``````Answer:
i=0
def hailstone( n ) :  # hailstone sequence starting at a positive integer n
if n == 1 :
return 1
elif n % 2 == 0 :  #even
print( int(n ) , end=" , ")
return hailstone( n / 2 )
else :
print( int(n ) , end=" , ")
return hailstone( 3 * n + 1) #recursive function hailstone ( n)

#print(i)
n = int(input("Enter a number : "))
print ( hailstone( n ) )``````

Q.4. A happy number is a number in which the eventual sum of the square of the digits of the number is equal to 1.
Example : 12 = (1)2+(2)2 =1+4=5
Hence , 12 is not a happy number
Example 100 = (1)2 + ( 0 )2 + ( 0 )2 = 1+ 0 + 0 = 1
Hence , 100 is a happy number.
Write a program that takes a number and checks if it is a happy number by using following two functions in it :

Sum_sq_digits :returns the sum of the square of the digits of the number x, using the recursive technique
Ishappy() : checks if the given number is a happy number by calling the function sum_sq_digits and displays an appropriate message

``````Answer:
i=0
def sum_sq_digits (num,n= 0):
if n == len(num) :
return 0
else :
return ( int ( num [ n ] ) ) ** 2 + sum_sq_digits (num,n+1)

def Ishappy( num ):  # checks if  happy number
if sum_sq_digits (num) == 1 :
print("Happy number ")  # printing happy number

elif len(num) == 1 :
print("Not happy number ") #priinting not a happy number

else :
num = str( sum_sq_digits (num) )
Ishappy( num )
#Print(i)``````

Q.5. A list namely Adm stores admission numbers of 100 students in it, sorted in ascending order of admission numbers. Write a program that takes an admission number and looks for it in list Adm using binary search technique. The binary search function should use recursion in it.

``````Answer:
i=0
def ad ( adm , num , low = 0 , high = 9 ):  # Adm stores admission numbers of 100 students in it,
mid = int((low + high)/2)
if num == adm[mid] :
return num,"exit in on index  number : ",mid
elif num < adm[ mid ] :  #order of admission numbers. Write a program that takes an admission number and looks for it #in list Adm using binary search technique
high = mid-1
return ad ( adm , num , low , high )
elif num < adm[ mid ] :
low = mid + 1
return ad ( adm , num , low , high )
else :
return num,"is not exist in adm" #The binary search function should use recursion in it

#print(i)
adm = eval(input("Enter list of 100 student : "))
num = int(input("Enter a number : "))
print(  ad ( adm , num) )``````

Thanks for visit and study the Recursion in Python Solutions for CBSE Class 12.

Click below for other chapters solutions
Computer Science with Python Class 12 Sumita Arora Solutions – CS Study