CSE225 Data Structures Homework 1 -Solved

1) We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3, ..) have the normal 
2 ears. The even bunnies (2, 4, ..) have 3 ears, because they each have a raised foot. Recursively 
return the number of “ears” in the bunny line 1, 2, ... n (without loops or multiplication). 
Example: 
Please enter the number of lines (n=): 2 
bunnyEars2(0) → 0 
bunnyEars2(1) → 2 
bunnyEars2(2) → 5 
2) In this question, you will write a program to find super digit of a number X using the following 
rules: 
• If X has only 1 digit, then its super digit is X. 
• If X has more than 1 digit, then its super digit is equal to the super digit of the digit-sum of X. 
Example: 
superDigit(1245) = superDigit(1+2+4+5) 
 = superDigit(12) 
 = superDigit(1+2) 
 = superDigit(3) 
 = 3. 
• The number X will be given to your program with two numbers (n and k) and you will 
construct the number X as the number n concatenated k times. 
Example: 
Please enter a number (n=) : 123 
Please enter repetition factor (k=) : 3 
Super digit of number 123123123 is 9.A
3) In this question, you will print identical triangles nested each other recursively. You will construct 
the triangles by using two digits ‘_’(underscore) and ‘1’. There will be number of iterations given 
as an input to your program. 
• If the number of iterations is given as 0, you will print a simple triangle by using 32 rows and 
63 columns in a matrix as the following: 
_______________________________1_______________________________ 
______________________________111______________________________ 
_____________________________11111_____________________________ 
____________________________1111111____________________________ 
___________________________111111111___________________________ 
__________________________11111111111__________________________ 
_________________________1111111111111_________________________ 
________________________111111111111111________________________ 
_______________________11111111111111111_______________________ 
______________________1111111111111111111______________________ 
_____________________111111111111111111111_____________________ 
____________________11111111111111111111111____________________ 
___________________1111111111111111111111111___________________ 
__________________111111111111111111111111111__________________ 
_________________11111111111111111111111111111_________________ 
________________1111111111111111111111111111111________________ 
_______________111111111111111111111111111111111_______________ 
______________11111111111111111111111111111111111______________ 
_____________1111111111111111111111111111111111111_____________ 
____________111111111111111111111111111111111111111____________ 
___________11111111111111111111111111111111111111111___________ 
__________1111111111111111111111111111111111111111111__________ 
_________111111111111111111111111111111111111111111111_________ 
________11111111111111111111111111111111111111111111111________ 
_______1111111111111111111111111111111111111111111111111_______ 
______111111111111111111111111111111111111111111111111111______ 
_____11111111111111111111111111111111111111111111111111111_____ 
____1111111111111111111111111111111111111111111111111111111____ 
___111111111111111111111111111111111111111111111111111111111___ 
__11111111111111111111111111111111111111111111111111111111111__ 
_1111111111111111111111111111111111111111111111111111111111111_ 
111111111111111111111111111111111111111111111111111111111111111Asso
3/7 
• If the number of iterations is given as 1, you will create 3 triangles by calculating their 3 
corner points using the original triangle in the previous iteration. It should be noted that the 
original triangle at iteration 0 will be decomposed three identical triangles as the following: 
_______________________________1_______________________________ 
______________________________111______________________________ 
_____________________________11111_____________________________ 
____________________________1111111____________________________ 
___________________________111111111___________________________ 
__________________________11111111111__________________________ 
_________________________1111111111111_________________________ 
________________________111111111111111________________________ 
_______________________11111111111111111_______________________ 
______________________1111111111111111111______________________ 
_____________________111111111111111111111_____________________ 
____________________11111111111111111111111____________________ 
___________________1111111111111111111111111___________________ 
__________________111111111111111111111111111__________________ 
_________________11111111111111111111111111111_________________ 
________________1111111111111111111111111111111________________ 
_______________1_______________________________1_______________ 
______________111_____________________________111______________ 
_____________11111___________________________11111_____________ 
____________1111111_________________________1111111____________ 
___________111111111_______________________111111111___________ 
__________11111111111_____________________11111111111__________ 
_________1111111111111___________________1111111111111_________ 
________111111111111111_________________111111111111111________ 
_______11111111111111111_______________11111111111111111_______ 
______1111111111111111111_____________1111111111111111111______ 
_____111111111111111111111___________111111111111111111111_____ 
____11111111111111111111111_________11111111111111111111111____ 
___1111111111111111111111111_______1111111111111111111111111___ 
__111111111111111111111111111_____111111111111111111111111111__ 
_11111111111111111111111111111___11111111111111111111111111111_ 
1111111111111111111111111111111_1111111111111111111111111111111Assoc.P
4/7 
• If the number of iterations is given as 2, you will again create 3 triangles for each triangle in 
the previous iteration by calculating their 3 corner points using the triangles in the previous 
iteration. It should be noted that each triangle at iteration 1 will be decomposed three 
identical triangles as the following: 
_______________________________1_______________________________ 
______________________________111______________________________ 
_____________________________11111_____________________________ 
____________________________1111111____________________________ 
___________________________111111111___________________________ 
__________________________11111111111__________________________ 
_________________________1111111111111_________________________ 
________________________111111111111111________________________ 
_______________________1_______________1_______________________ 
______________________111_____________111______________________ 
_____________________11111___________11111_____________________ 
____________________1111111_________1111111____________________ 
___________________111111111_______111111111___________________ 
__________________11111111111_____11111111111__________________ 
_________________1111111111111___1111111111111_________________ 
________________111111111111111_111111111111111________________ 
_______________1_______________________________1_______________ 
______________111_____________________________111______________ 
_____________11111___________________________11111_____________ 
____________1111111_________________________1111111____________ 
___________111111111_______________________111111111___________ 
__________11111111111_____________________11111111111__________ 
_________1111111111111___________________1111111111111_________ 
________111111111111111_________________111111111111111________ 
_______1_______________1_______________1_______________1_______ 
______111_____________111_____________111_____________111______ 
_____11111___________11111___________11111___________11111_____ 
____1111111_________1111111_________1111111_________1111111____ 
___111111111_______111111111_______111111111_______111111111___ 
__11111111111_____11111111111_____11111111111_____11111111111__ 
_1111111111111___1111111111111___1111111111111___1111111111111_ 
111111111111111_111111111111111_111111111111111_111111111111111Assoc.Prof.
• If the number of iterations is given as 3, you will need to print triangles as the following: 
_______________________________1_______________________________ 
______________________________111______________________________ 
_____________________________11111_____________________________ 
____________________________1111111____________________________ 
___________________________1_______1___________________________ 
__________________________111_____111__________________________ 
_________________________11111___11111_________________________ 
________________________1111111_1111111________________________ 
_______________________1_______________1_______________________ 
______________________111_____________111______________________ 
_____________________11111___________11111_____________________ 
____________________1111111_________1111111____________________ 
___________________1_______1_______1_______1___________________ 
__________________111_____111_____111_____111__________________ 
_________________11111___11111___11111___11111_________________ 
________________1111111_1111111_1111111_1111111________________ 
_______________1_______________________________1_______________ 
______________111_____________________________111______________ 
_____________11111___________________________11111_____________ 
____________1111111_________________________1111111____________ 
___________1_______1_______________________1_______1___________ 
__________111_____111_____________________111_____111__________ 
_________11111___11111___________________11111___11111_________ 
________1111111_1111111_________________1111111_1111111________ 
_______1_______________1_______________1_______________1_______ 
______111_____________111_____________111_____________111______ 
_____11111___________11111___________11111___________11111_____ 
____1111111_________1111111_________1111111_________1111111____ 
___1_______1_______1_______1_______1_______1_______1_______1___ 
__111_____111_____111_____111_____111_____111_____111_____111__ 
_11111___11111___11111___11111___11111___11111___11111___11111_ 
1111111_1111111_1111111_1111111_1111111_1111111_1111111_1111111Assoc.
6/7 
• If the number of iterations is given as 4, you will need to print triangles as the following: 
_______________________________1_______________________________ 
______________________________111______________________________ 
_____________________________1___1_____________________________ 
____________________________111_111____________________________ 
___________________________1_______1___________________________ 
__________________________111_____111__________________________ 
_________________________1___1___1___1_________________________ 
________________________111_111_111_111________________________ 
_______________________1_______________1_______________________ 
______________________111_____________111______________________ 
_____________________1___1___________1___1_____________________ 
____________________111_111_________111_111____________________ 
___________________1_______1_______1_______1___________________ 
__________________111_____111_____111_____111__________________ 
_________________1___1___1___1___1___1___1___1_________________ 
________________111_111_111_111_111_111_111_111________________ 
_______________1_______________________________1_______________ 
______________111_____________________________111______________ 
_____________1___1___________________________1___1_____________ 
____________111_111_________________________111_111____________ 
___________1_______1_______________________1_______1___________ 
__________111_____111_____________________111_____111__________ 
_________1___1___1___1___________________1___1___1___1_________ 
________111_111_111_111_________________111_111_111_111________ 
_______1_______________1_______________1_______________1_______ 
______111_____________111_____________111_____________111______ 
_____1___1___________1___1___________1___1___________1___1_____ 
____111_111_________111_111_________111_111_________111_111____ 
___1_______1_______1_______1_______1_______1_______1_______1___ 
__111_____111_____111_____111_____111_____111_____111_____111__ 
_1___1___1___1___1___1___1___1___1___1___1___1___1___1___1___1_ 
111_111_111_111_111_111_111_111_111_111_111_111_111_111_111_111 
• The number of iterations given to your program will be less than 5. 
• The output will consist of 32 rows and 63 columns, and will be composed of ones (1) and 
underscores (_) as in the triangles above. 
• Solutions using iterations will not be graded for ALL questions. 
• You have to solve the problems by using RECURSION. 
• It should be noted that selected parts will be graded in your homework.Assoc.Prof.Dr. Mustafa AĞAOĞLU