# Recursive sum and recursive display of triangle

Objective

Homework 6 is designed to give you lots of practice with recursion, recursion, and recursion. You should think carefully about the base case(s), recursive case(s), and recursive call(s) that each problem will need.

hw6_part1.py

Create a program that calculates the summation of a number, stopping at a second number (specified by the user) rather than at 1. The program must contain a main() and a recursive function, the name of which is up to you.

The numbers entered by the user may be positive or negative. However, your program may assume that the second number entered is always lower than the first number entered.

Here is some sample output, with the user input in blue.
(Yours does not have to match this word for word, but it should be similar.)

bash-4.1\$ python hw6_part1.py Please input the number you want to sum from: 10 Please input the number you want to sum down to: 1 The summation from 10 to 1 is 55

bash-4.1\$ python hw6_part1.py Please input the number you want to sum from: 999 Please input the number you want to sum down to: 56 The summation from 999 to 56 is 497960

bash-4.1\$ python hw6_part1.py Please input the number you want to sum from: 15 Please input the number you want to sum down to: -80 The summation from 15 to -80 is -3120

bash-4.1\$ python hw6_part1.py Please input the number you want to sum from: -1 Please input the number you want to sum down to: -10 The summation from -1 to -10 is -55

hw6_part2.py

Next, you will create a program that is the recursive version: drawing a right triangle, using a height and symbol provided by the user.

The program must contain a main() and a recursive function called recurTri(). The program may also contain any other functions you deem necessary.

For these inputs, you can assume the following:

• The height will be a positive integer (zero or greater)
• The symbol will be a single character

Here is some sample output, with the user input in blue.
(Yours does not have to match this word for word, but it should be similar.)

bash-4.1\$ python hw6_part2.py Please enter the height of the triangle: 8 Please enter the symbol to use: o

o

oo

ooo

oooo

ooooo

oooooo

ooooooo

oooooooo

bash-4.1\$ python hw6_part2.py Please enter the height of the triangle: 1 Please enter the symbol to use: W

W

bash-4.1\$ python hw6_part2.py Please enter the height of the triangle: 0 Please enter the symbol to use: d

hw6_part3.py

For this part of the homework, you will write a recursive function that counts the number of ears and horns in a line of horses and unicorns. (Horses have 2 ears, while unicorns have 2 ears and a horn, for a total of 3.) The unicorns and horses alternate in the line, with a unicorn in the first position, a horse in the second, etc. The user will enter the length of the line of equines; it is guaranteed to be a positive number (zero or higher).

The program must contain a main() and a recursive function called count(). The count() function will take in an integer (the line length) and, through recursion, return the total number of ears and horns. The program may also contain any other functions you deem necessary.

Here is some sample output, with the user input in blue.
(Yours does not have to match this word for word, but it should be similar.)

bash-4.1\$ python hw6_part3.py

How long is the line of equines? 0

In a line of 0 equines, there are 0 ears and horns.

bash-4.1\$ python hw6_part3.py

How long is the line of equines? 10

In a line of 10 equines, there are 25 ears and horns.

bash-4.1\$ python hw6_part3.py

How long is the line of equines? 2

In a line of 2 equines, there are 5 ears and horns.

bash-4.1\$ python hw6_part3.py

How long is the line of equines? 3

In a line of 3 equines, there are 8 ears and horns.

bash-4.1\$ python hw6_part3.py

How long is the line of equines? 88

In a line of 88 equines, there are 220 ears and horns.

bash-4.1\$ python hw6_part3.py

How long is the line of equines? 980

In a line of 980 equines, there are 2450 ears and horns.

hw6_part4.py

Create a program that asks the user for a word, and then checks to see if that word is a palindrome. When checking for a palindrome, the program should be case insensitive. If the word is not a palindrome, the program must print out the reversed word in the message.

The program must contain a main() and a recursive function called reverseStr(). The reverseStr() function will take in a string and, through recursion, return that string in reverse. The program may also contain any other functions you deem necessary.

Here is some sample output, with the user input in blue.
(Yours does not have to match this word for word, but it should be similar.)

bash-4.1\$ python hw6_part1.py

Please enter a word to check for palindrome-ness: UMBC

Sorry, the word UMBC is NOT a palindrome.

Backwards, it becomes CBMU.

bash-4.1\$ python hw6_part1.py
Please enter a word to check for palindrome-ness: racecar

The word racecar IS a palindrome.

bash-4.1\$ python hw6_part1.py
Please enter a word to check for palindrome-ness: TacoCat

The word TacoCat IS a palindrome.

bash-4.1\$ python hw6_part1.py
Please enter a word to check for palindrome-ness: taco cat

Sorry, the word taco cat is NOT a palindrome.
Backwards, it becomes tacocat.

Part 5 and Part 6 will both tackle the problem of generating the levels of a Pascal’s triangle. Part 5 must contain a NON-recursive solution to the problem, while Part 6 must contain a RECURSIVE solution. You may tackle them in either order, but we recommend Part 5 first.

hw6_part5.py

The last program will generate the levels of Pascal’s triangle.

The program must contain a main() and a NON-recursive function called pascal(), implemented as described in the function header comment given below.

#############################################################   # pascal() creates each level of Pascal’s   #          triangle, reaching the requested height   # Input:   levelsToMake; an int, the number of levels requested   # Output:  None (the levels are printed from the function)

Your code must perform basic input validation to ensure that numbers are greater than or equal to 1, and tell the user what it will accept as valid input.

Note that the code should follow the conventional numbering of a Pascal’s triangle: the first row (the single 1 at the top) is row zero, meaning that a request for a triangle of height 5 will result in six rows being printed out.

It is also highly recommended that you create a Pascal’s triangle by hand (to a height of at least 8).

(You do not need to worry about printing out a “centered” triangle – the numbers being left-aligned (as seen in the sample output) is acceptable.)

hw6_part6.py

The last program will use recursion to generate the levels of Pascal’s triangle.

The program must contain a main() and a recursive function called pascal(), implemented as described in the function header comment given below.

#############################################################   # pascal() uses recursion to create each level of Pascal’s

#             triangle, reaching the requested height

# Input: currLevel;    an int, the current level being created

#             levelsToMake; an int, the number of levels requested

#             levelList;    a 2D list of ints, containing the levels as they

#                             are created

#

# Output:  None (levelList is changed in place, and the updated

levelList will be the same in main() )

Your code must perform basic input validation to ensure that numbers are greater than or equal to 1, and tell the user what it will accept as valid input.

The code should follow the conventional numbering of a Pascal’s triangle: the first row (the single 1 at the top) is row zero, meaning that a request for a triangle of height 5 will result in six rows being generated in total.

It is also highly recommended that you create a Pascal’s triangle by hand (to a height of at least 8), paying attention to the steps taken as you go, prior to beginning your code.

Here is the sample output for hw6_part5.py and hw6_part6.py with the user input in blue.
(Yours does not have to match this word for word, but it should be similar.)

bash-4.1\$ python hw6_part5.py
Welcome to the Pascal’s triangle generator.

Please enter the number of levels to generate: -1

Your number must be positive (greater than zero). Please enter the number of levels to generate: 0

Your number must be positive (greater than zero). Please enter the number of levels to generate: 1

1
11

bash-4.1\$ python hw6_part6.py
Welcome to the Pascal’s triangle generator.

Please enter the number of levels to generate: 6

1
11
121
1331
14641
1 5 10 10 5 1
1 6 15 20 15 6 1

bash-4.1\$ python hw6_part5.py
Welcome to the Pascal’s triangle generator.
Please enter the number of levels to generate: 13

1
11
121
1331
14641
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1

Solution

hw6_part1.py

defsum_numbers(a, b):

if a == b:  # base case

return a

else:       # add this number to the sum of the rest

return a + sum_numbers(a – 1, b)

def main():

beg = int(input(“Please input the number you want to sum from: “))

end = int(input(“Please input the number you want to sum down to: “))

total = sum_numbers(beg, end)

print(“The summation from {} to {} is {}”.format(beg, end, total))

if __name__ == ‘__main__’:

main()

hw6_part2.py

# prints a single row of symbols

defrecurRow(width, symbol):

if width == 0:

print()

else:

print(symbol, end=”)

recurRow(width – 1, symbol)

defrecurTri(height, symbol):

if height == 0:

return

else:

recurTri(height – 1, symbol)    # print the row on the top of this

recurRow(height, symbol)        # print this row

def main():

height = int(input(“Please enter the height of the triangle: “))

symbol = input(“Please enter the symbol to use: “)

recurTri(height, symbol)

if __name__ == ‘__main__’:

main()

hw6_part3.py

def count(number):

if number == 0:

return 0

elif number % 2 == 1:   # unicorn

return 3 + count(number – 1)

else:                   # horse

return 2 + count(number – 1)

def main():

number = int(input(“How long is the line of equines? “))

print(“In a line of {} equines, there are {} ears and horns.”.format(number, count(number)))

if __name__ == ‘__main__’:

main()

hw6_part4.py

defreverseStr(s):

if s == ”:

return s

else:   # append the first character to the end of the reversed tail

returnreverseStr(s[1:]) + s

def main():

word = input(“Please enter a word to check for palindrome-ness: “)

if word == reverseStr(word):

print(‘The word {} IS a palindrome.’.format(word))

else:

print(‘Sorry, the word {} is NOT a palindrome.’.format(word))

print(‘Backwards, it becomes {}.’.format(reverseStr(word)))

if __name__ == ‘__main__’:

main()

hw6_part5.py

#############################################################

# pascal() creates each level of Pascal’s

#          triangle, reaching the requested height

# Input:   levelsToMake; an int, the number of levels requested

defpascal(levelsToMake):

print(1)        # print prevLevel

for i in range(levelsToMake):

# construct a new level of Pascal’s

# triangle based on the previous

thisLevel =      # leading 1

for j in range(1, len(prevLevel)):

thisLevel.append(prevLevel[j – 1] + prevLevel[j])

thisLevel.append(1) # training 1

fornum in thisLevel:   # print thisLevel

print(num, end=’ ‘)

print()

# thisLevel becomes previous on the next step

prevLevel = thisLevel

def main():

print(“Welcome to the Pascal’s triangle generator.”)

print()

levels = 0

while levels <= 0:

levels = int(input(“Please enter the number of levels to generate: “))

if levels < 0:

print(“Your number must be positive (greater than zero).”)

pascal(levels)

if __name__ == ‘__main__’:

main()

hw6_part6.py

#############################################################

# pascal() uses recursion to create each level of Pascal’s

#     triangle, reaching the requested height

# Input: currLevel;    an int, the current level being created

#     levelsToMake; an int, the number of levels requested

#     levelList;    a 2D list of ints, containing the levels as they

#           are created

#

# Output:  None (levelList is changed in place, and the updated

#     levelList will be the same in main() )

defpascal(currLevel, levelsToMake, levelList):

ifcurrLevel>levelsToMake:

return

else:

# construct a new level of Pascal’s

# triangle based on the previous

prevLevel = levelList[-1]

thisLevel =      # leading 1

for j in range(1, len(prevLevel)):

thisLevel.append(prevLevel[j – 1] + prevLevel[j])

thisLevel.append(1) # training 1

ifcurrLevel<levelsToMake:

levelList.append(thisLevel)

fornum in prevLevel:   # print previous level

print(num, end=’ ‘)

print()

pascal(currLevel + 1, levelsToMake, levelList)

def main():

print(“Welcome to the Pascal’s triangle generator.”)

print()

levels = 0

while levels <= 0:

levels = int(input(“Please enter the number of levels to generate: “))

if levels < 0:

print(“Your number must be positive (greater than zero).”)

pascal(0, levels, [])

if __name__ == ‘__main__’:

main()