HOMEWORK 11: RECURSION Solution

The goal of this homework is to allow you to practice and understand how to use recursion to solve problems. Refer to the rubric to see how points will be rewarded for each function. You have been given HW11.py to fill out with instructions in the docstrings. However, below you will find more detailed information on how to complete the assignment.   
NOTE: YOU MUST USE RECURSION TO WRITE EVERY FUNCTION (NOT ITERATION) TO RECEIVE CREDIT FOR THIS ASSIGNMENT!

Function name: leaning_pyramid

Parameters: int
Returns: None

Description: Write a function that takes in a positive integer n (n ≥ 1). Use this integer to draw a leaning pyramid made out of stars (*). The base of the pyramid will consist of n stars, the next level of the pyramid will consist of n - 1 stars, etc. The top will be a single star.

Test Cases:

    • leaning_pyramid(5)

*

**
***

****
*****

    • leaning_pyramid(3)

*
**

***

Function name: reverse_phrase

Parameters: string
Returns: string
Description: Write a function that accepts one parameter, a string. Use recursion to reverse all the characters in the phrase. Keep in mind that you are reversing the entire string regardless of what it contains.

Test Cases:

    • test_one = reverse_phrase("car")

    • print(test_one)
rac

    • test_two = reverse_phrase("Karoline likes chocolate")

    • print(test_two)

etalocohc sekil eniloraK

    • test_three = reverse_phrase("123456789")

    • print(test_three)

987654321


Function name: find_parenthesized_string

Parameters: string
Returns: string

Description: Given a string that contains a single pair of parenthesis, compute recursively a new string made up of only the parenthesis and the contents between them. Assume the single pair of parentheses will always be included in the string and that no other parenthesis will exist in the string. Return the computed string. You may not use .find in your solution.

Test Cases:

    • test_one = find_parenthesized_string('(cs1301)abcdefg')

    • print(test_one)

(cs1301)

>>> test_two =

find_parenthesized_string('aaldsfj(riverdale)lkjadlksfj')

    • print(test_two) (riverdale)

    • test_three = find_parenthesized_string('()')

    • print(test_three)

()

Function name: factorial_dictionary

Parameters: int
Returns: dict

Description: Define a recursive function that accepts a positive integer parameter n (n ≥ 1) and returns a dictionary. The dictionary should contain, as a key, every number from 1 to the number passed in (inclusive). The corresponding value for each key should be the factorial of that number. You may not use looping in your solution.

Hint: When trying to solve factorial_dictionary(n), you first need to recursively get factorial_dictionary(n – 1). How would you get from factorial_dictionary(n – 1) to factorial dictionary(n)?

Test Cases:

    • test_one = factorial_dictionary(5)

    • print(test_one)
{1: 1, 2: 2, 3: 6, 4: 24, 5: 120}

    • test_two = factorial_dictionary(2)

    • print(test_two)
{1: 1, 2: 2}


    • test_three = factorial_dictionary(1)

    • print(test_three)

{1: 1}

Function name: pascal_triangle

Parameters: int
Returns: list of ints

Description: Write a function that takes in an integer parameter n (n ≥ 0) and returns a list of the elements of that row (the nth row) in the Pascal Triangle. Here is a link to what a Pascal Triangle looks like, and the rules behind making one: http://mathforum.org/workshops/usi/pascal/pascal_intro.html!

Hint: When trying to solve pascal_triangle(n), you first need to recursively get pascal_triangle(n – 1). How would you get from pascal_triangle(n – 1) to pascal_triangle(n)?

Test Cases:

    • test_one = pascal_triangle(6)

    • print(test_one)
[1, 6, 15, 20, 15, 6, 1]

    • test_two = pascal_triangle(10)

    • print(test_two)
[1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1]

    • test_three = pascal_triangle(0)

    • print(test_three)

[1]
CS1301 - HOMEWORK 11: RECURSION




Grading Rubric

NOTE: ALL FUNCTIONS IN THIS HOMEWORK MUST BE SOLVED USING RECURSION OR NO CREDIT WILL BE RECEIVED FOR THAT FUNCTION.

leaning_pyramid:
10
pts
reverse_phrase:
20
pts
find_parenthesized_string:
20
pts
factorial_dictionary:
25
pts
pascal_triangle:
25
pts


Provided

The following file(s) have been provided to you.

1.  HW11.py

This is the file you will edit and implement. All instructions for what the methods should do are in the docstrings.

Deliverables

You must submit all of the following file(s). Please make sure the filename matches the filename(s) below. Be sure you receive the confirmation email from T-Square, and then download your uploaded files to a new folder and run them.

1.  HW11.py

If this file does not run (if it encounters an error while trying to run), you will get no credit on the assignment.