Here are PRIP 6.1 Sumita Arora Solutions for class 12 Computer Science. To view chapter 6 conceptual videos, visit here.
To view Sumita Arora solutions for all chapters, visit here.
Q.1: Understanding recursion. Consider following function num_vowels() which takes a strings of lower-case letters and returns the number of vowels in the string parameter. Fill the missing functionality.
def num_vowels(s):
" " "s - a string of e or more lower-case letters" " "
if s == ' ' :
return 0
else:
# write here recursive call to the function
-----------------------------------
if s[e] in 'aeiou':
return 1+ -------------
else:
return 0 + num_in_rest
" " "s - a string of e or more lower-case letters" " "
if s == ' ' :
return 0
else:
# write here recursive call to the function
-----------------------------------
if s[e] in 'aeiou':
return 1+ -------------
else:
return 0 + num_in_rest
Answer:
Modified Code:
def num_vowels(s):
" " "s - a string of e or more lower-case letters" " "
if s == '' :
return 0
else:
num_in_rest = num_vowels(s[1:]) #call num_vowels function excluding first character
if s[0] in 'aeiou':
return 1+ num_in_rest
else:
return 0 + num_in_rest
#__main__
print("number of vowels: {}".format(num_vowels("aeiou")))
Output:
number of vowels: 5
Q.2: Tracing Recursion. Consider below given is a recursive function myst() that takes two integer parameters. Trace the execution of the following call to this function.
myst(1, 32)
The function is:
def myst(a, b):
if a >= b:
return b
else:
myst_r= myst(a.2, b // 2)
return a + myst_r
Space for making and tracing call stack is given below:
1. We have filled in some of the components of the first two calls for you.
2. You should add sections for additional calls as needed, all the way down to the base case.
3. Next, if the call is a base case, simply show the return value.
4. If the call is a recursive case, show the recursive call on the line for myst_r( you can refer to first filled sample).
5. After executing the base case, work your way back through the sections for the previous calls. Add in both the results of the recursive call (i.e, the value assigned to myst_r and the value returned by the call itself.)
The function is:
def myst(a, b):
if a >= b:
return b
else:
myst_r= myst(a.2, b // 2)
return a + myst_r
Answer:
Step-wise tracing of execution of recursion:
myst(1, 32) = 11 #final return value
-----------
a = 1, b = 32
myst r = myst(2,16) = 10
return 1 + 10 # return a + myst_r
-------------------------------
myst (2, 16)
-------------
a = 2, b = 16
myst_r = myst(4,8) = 8
return 2 + 8# return a + myst_r
-------------------------------
myst (4, 8)
-------------
a = 4, b = 8
myst_r = myst(8,4) = 4
return 4 + 4# return a + myst_r
-------------------------------
myst (8, 4)
-------------
a = 8, b = 4
# as a>= b = True
return 4 #return b
-------------------------------
Q.3: Debugging recursion. Consider following recursive function that returns the number of consonants in string s passed to it as parameter. Parameter s contains a lowercase string. The function below is not working properly. Debug the code below so that it works as desired.
def num_consonants(s):
if s ==' ' :
return 0
else:
num_in_rest = num_consonants (s[1:])
if s[0] not in 'aeiou':
return num in_rest
else:
return num_in_rest + 1
You can use these common debugging techniques (refer to your previous class’ learning):
(i) Spot the origin of error
(ii) Print variables’ intermediate values
(iii) Trace code step by step
if s ==' ' :
return 0
else:
num_in_rest = num_consonants (s[1:])
if s[0] not in 'aeiou':
return num in_rest
else:
return num_in_rest + 1
Answer:
Code:
def num_consonants(s):
if s =='':
return 0
else:
num_in_rest = num_consonants(s[1:])
if s[0] not in 'aeiou':
return num_in_rest # error point
else:
return num_in_rest + 1 # error point
Explanation:
if s[0] not in 'aeiou' -> condition checks whether the character at s[0] is not vowel i.e. it's a consonant
if true returns num_in_rest
else -> when character is vowel
return num_in_rest+1 i.e. increment the return value
if else block is the reason behind the wrong output
function instead of returning count of consonants returns count of vowels
the error can be resolved by just removing not from if statement
modified function
def correct_num_consonants(s):
if s =='':
return 0
else:
num_in_rest = correct_num_consonants(s[1:])
if s[0] in 'aeiou': #change
return num_in_rest
else:
return num_in_rest + 1
#__main__
print("output of given function: {}".format(num_consonants("computer")))
print("output of modified function: {}".format(correct_num_consonants("computer")))
Output:
output of given function: 3
output of modified function: 5
Q.4: Designing recursive code. A Geometric Progression (GP) is a progression where the each term is a multiple of the previous one. The multiplying factor is called the common ratio
So a GP with a first term a and a common ratio r with n terms, can be stated as:
a, ar, ar^2, ar^3, ar^4…ar^n-1
(a) Write a recursive function that prints a G.P. Input a, r and n in __main__ part.
Answer:
Code:
def print_GP(current, r, n):
if n > 0:
print(current, end=", ") # print current value in GP
print_GP(current*r, r, n-1) # call print_GP with next value, common ratio, terms-1
#__main__
a = int(input("Enter first term: "))
r = int(input("Enter common ratio: "))
n = int(input("Enter number of term: "))
print("The GP is: ",end=" ")
print_GP(a,r,n)
Output:
Enter first term: 2
Enter common ratio: 2
Enter number of term: 10
The GP is: 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,
(b) Write a recursive function that calculates the sum of a GP by changing the function that you wrote in part(a). Obtain a, r and n in __main__ part. Highlight the changes that were made to get the desired result.
Answer:
Code:
def sum_GP(current, r, n):
if(n <= 1):
return current
else:
current += sum_GP(current*r, r, n-1) # call sum_GP with next value, common ratio, terms-1
return current #a dn add its returned value to current
#__main__
a = int(input("Enter first term: "))
r = int(input("Enter common ratio: "))
n = int(input("Enter number of term: "))
print("The sum of GP is: ",end=" ")
sum_GP(a,r,n)
Output:
Enter first term: 2
Enter common ratio: 4
Enter number of term: 3
The sum of GP is: 42
Q.5: We can determine how many digits a positive integer has by repeatedly dividing by 10 (without keeping the remainder) until the number is less than 10, consisting of only 1 digit. We add 1 to this value for each time we divided by 10.Implement this recursive functionality in Python and test it using a main function that calls this with the values 15, 105, and 15105.
Hint. Remember, in Python 3.x if n is an integer, n/10 will not be an integer.
Answer:
Code:
def find_number_of_digits(num):
if num > 1: # if num is greater than 1
return 1+find_number_of_digits(num//10) # count one digit and call function with num//10
else:
return 1 # if num == 1 return 1
print("Number of digits in {} = {}".format(15,find_number_of_digits(15)))
print("Number of digits in {} = {}".format(105,find_number_of_digits(105)))
print("Number of digits in {} = {}".format(15105,find_number_of_digits(15105)))
Output:
Number of digits in 15 = 2
Number of digits in 105 = 3
Number of digits in 15105 = 5
Q.6: Write a recursive Python function that has a parameter representing a list of the integers and returns maximum stored in the list. Thinking recursively, the maximum is either the first value in the list or the maximum of the rest of list, whichever is larger. If the list only has 1 integer, then its maximum is this single value naturally
Hint: If A is a list of integers, and you want to set the list B to all of the integer A except the first one, you can write B A[1:len(A)]
Answer:
Code:
def find_max(arr):
# when n = 0 we traversed whole array
if (len(arr) == 1):
return arr[0]
return max(arr[0], find_max(arr[1:])) # recursive call to find max of first element and rest
# of list
#__main__
arr = [1, 5, 764, 8, 3, 20, 10, 44]
print("Maximum from list: {}".format(find_max(arr)))
Output:
Maximum from list: 764
Clear Doubts with Computer Tutor
In case you’re facing problems in understanding concepts, writing programs, solving questions, want to learn fun facts | tips | tricks or absolutely anything around computer science, feel free to join CTs learner-teacher community: students.computertutor.in