Lesson16 Individual Assignment

Individual means that you do it yourself. You won't learn to code if you don't struggle for yourself and write your own code. Remember that while you can discuss the general (algorithmic) way to solve a problem, you should not even be looking at anyone else's code or showing anyone else your code for an individual assignment.
Review the Group Work guidelines on Cavas and/or ask an instructor if you have any questions.

Programming Practice

Be sure to spell all function names correctly - misspelled functions will lose points (and often break anyway since no one is sure what to type to call it). If you prefer showing your earlier, scratch work as you figure out what you are doing, please be sure that you make a final, complete, correct last function in its own cell that you then call several times to test. In other words, separate your thought process/working versions from the final one (a comment that tells us which is the final version would be lovely).

Every function should have at least a docstring at the start that states what it does (see Lesson3 Team Notebook if you need a reminder). Make other comments as necessary.

Make sure that you are running test cases (plural) for everything and commenting on the results in markdown. Your comments should discuss how you know that the test case results are correct.

part 1: Recursive summation

In part 1 you will define and test a recursive_summation function. We thought about summation in the Team Notebook, review that info if you need to.

A. Write test cases for your function - fill in the table below before you start coding! Fill in the expected and rationale for all, and more test cases for the extra $n$s below - at least one more should be negative, the rest positive.

B. Define and test a recursive_summation function that:

• takes a single parameter n and
• returns the summation $\displaystyle \left(\sum_{i=1}^{n}i\right)$ using recursion for positive integers
• returns any number you wish for negative numbers, but it should not crash
• your recursive_summation function should:
  • have an if-else statement
  • not have any loops
  • not print anything in its final version, if you use prints to help you debug, you should comment them out once your function works correctly.

Make sure to run all of the test cases above, leave in the results, and comment on the results.

part 2: Recursive power

In this part, you will define a recursive power function that takes two numbers as parameters, $x$ and $n$ ($x$ can be any integer, but $n$ should be positive), calculates and returns $x^n$. Use the following recursive definitions:

$x^n = (x^{n/2})^2 \hspace{20mm} \text{when n is even}$
$x^n = x \cdot(x^{(n-1)/2})^2 \hspace{8.5mm} \text{when n is odd}$
$x^0 = 1 \hspace{30mm} \text{when n is 0}$

Further considerations:

• remember, $x$ can be any integer, but $n$ should be positive
• notice that there are multiple cases, so you should use an if-elif-else in your recursive function.
• you should not use any loops, nor should you use the ** operator in this function.
• you also must use the above recursive definitions (using another algorithm will not earn you full credit on this function).

C. Write test cases for your function - fill in the table below before you start coding! Fill in the expected and rationale for all and more test cases for the extra $x$s and $n$s below.

D. Design a recursive power function using the above equations, by answering the following questions:

• How can you define power in terms of a smaller similar problem? In other words, how will having a solution to the smaller problem help you answer the original problem?
• For each recursive call, how will you make the problem size smaller?
• What is the base case, where you solve an easy problem in one step?
• What will you do for the base case?

E. Define and test a recursive power function that meets all the criteria above and correctly executes all of the tests. Make sure to comment on your results.

part 3: Permutations and combinations

Copy and paste your recursive factorial function below:

F. Before we use it inside another function, we need to clean it up.
Copy, paste, your recursive factorial function again below and edit so that it:

• it never prints
• only returns a value
• returns None for negative numbers

G. test the new version of factorial with:

• 0
• 1
• 5
• a negative value
• 2 more positive values

comment on the results.

Review the information on permutations and combinations from preactivity

H. Design and write a new function gene_permutations that:

• takes 2 parameters:
  • a total number of genes in the organism ($n$)
  • the number of genes that you want to consider ($k$)
• returns the number of permutations of genes from total
• uses your factorial function

Write, predict the results of, and provide a rationale for at least 3 test cases for the above function before you write the code.

Provide your pseudocode here (this can be short):

I. write a new function gene_combinations that:

• takes 2 parameters:
  • a total number of genes in the organism ($n$)
  • the number of genes that you want to consider ($k$)
• returns the number of combinations of genes from total
• uses your factorial function

Write, predict the results of, and provide a rationale for at least 3 test cases for the above function before you write the code.

Provide your pseudocode here (this can be short):