<jupyter_start><jupyter_text>Chapter 03: Reading and writing to file, recursion and algorithmsThis lab sheet will allow us to read and write to text files (which lets us store information even after we close down Python) and introduce recursion.  TutorialWork through the following:--- 1. Recursion.[A video describing the concept.](https://youtu.be/xFQGaPeaFxg)[A video demo.](https://youtu.be/VDXYEJcksPs)It is possible to define functions recursively. This is similar to inductiveproofs in mathematics. To do this we need to consider two things:1. A recursive rule;2. A base case (that the recursive rule reduces to).As an example let us code the following function:\\[    f(n) = \sum_{i=0}^ni\\]We can see the **'recursive rule'**:\\[    f(n) = f(n-1) + n\\]We also know that the **'base case'** is:\\[    f(0) = 0\\]Now let us program this function using recursion:<jupyter_code>def sum_of_integers(n):
    """Sum of integers from 0 to n"""
    if n == 0:  # Base case
        return 0
    return sum_of_integers(n - 1) + n  # Recursive rule
sum_of_integers(3)<jupyter_output><empty_output><jupyter_text>Here is another example. The factorial function \\(n!=n\times(n-1)\times(n-2)...2\times 1\\) can be defined as:1. The base case: \\(0!=1\\)2. The recursive rule: \\(n!=n\times (n-1)!\\)Here is how to code this:<jupyter_code>def factorial(n):
    """Returns n! using recursion"""
    if n == 0:  # Base case
        return 1
    return n * factorial(n - 1)
for n in range(6):
    print(factorial(n))<jupyter_output>1
1
2
6
24
120<jupyter_text>Experiment with modifying the above code. 2. Writing to file.[A video describing the concept.](https://youtu.be/w-gEOEOLfiA)[A video demo.](https://youtu.be/jFS015bgRS0)All of the data we handle with variables, lists and dictionaries lives inthe ‘memory’ of a computer when our Python code is running. When the programstops running the data is lost. There will be occasions when we want to writeour data to a file on the hard drive of a computer (so that it is alwaysavailable even when we turn the computer off).To do this we need Python toopen a file (usually a basic text file), write strings to the text file andthen close the file. The following code opens (or creates a) text file in‘write mode’ (that’s what the w is for) and writes the numbers 1 to 10 to it:<jupyter_code>textfile = open('mytextfile.txt', 'w')  # Open the file in write mode
for i in range(1, 11):
    textfile.write(str(i) + "\n")
textfile.close()  # Close the file<jupyter_output><empty_output><jupyter_text>It is also possible to do it as below (so that we don't have to worry about closing the file).<jupyter_code>with open('mytextfile.txt', 'w') as textfile:
    for i in range(1, 11):
        textfile.write(str(i) + "\n")<jupyter_output><empty_output><jupyter_text>Modify the above code to write something different to file. 3. Reading files.[A video describing the concept.](https://youtu.be/rn21nG6TZlg)[A video demo.](https://youtu.be/jtU3dML5mqw)To read data from a file, we need to open the file in ‘read mode’:<jupyter_code>with open('mytextfile.txt', 'r') as textfile:
    string = textfile.read()
string<jupyter_output><empty_output><jupyter_text>This string is not particularly helpful. To transform the string to alist we can use the split method which separates a string on a givencharacter:<jupyter_code>data = string.split('\n')
data<jupyter_output><empty_output><jupyter_text>We see that we have a list of **strings** and also have a last empy item.Here we clean that up (converting the strings to integers and ignoring the last item):<jupyter_code>data = [int(e) for e in data[:-1]]
data<jupyter_output><empty_output><jupyter_text>--- Worked example[A video describing the concept.](https://youtu.be/WgmgK7K3WUM)[A video demo.](https://youtu.be/7245uwUjSkI)The Fibonacci sequence can be thought of as:1. The base case: \\(f(0)=f(1)=1\\)2. The recursive rule: \\(f(n)=f(n-1)+f(n-2)\\)Here is how to code this:<jupyter_code>def fibonacci(n):
    """Returns the nth fibonacci number using recursion"""
    if n in [0, 1]:  # Base case
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)  # Recursive rule
for n in range(10):
     print(fibonacci(n))<jupyter_output>1
1
2
3
5
8
13
21
34
55<jupyter_text>It can be shown that the Fibonacci sequence can also be given by:\\[    f(n) = \frac{\phi^{(n + 1)} - (-\phi)^{-(n + 1)}}{\sqrt{5}}\\]Where \\(\phi\\) is the golden ratio:\\[    \phi = \frac{1 + \sqrt{5}}{2}\\]Let us use the recursive function to verify that this formula is correct for the first 30 values of \\(n\\):<jupyter_code>import math  # This is a library that has various helpful function
phi = (1 + math.sqrt(5)) / 2
def alt_fibonacci(n):
    """Return the nth fibonacci number using the golden ratio formula"""
    return (phi ** (n + 1) - (-phi) ** (-(n + 1))) / (math.sqrt(5))<jupyter_output><empty_output><jupyter_text>As we did in the previous sheet let us write a function to check the formula:<jupyter_code>def check_formula(K):
    """Check the golden ratio formula"""
    return fibonacci(K) == round(alt_fibonacci(K), 1)
check_formula(3)<jupyter_output><empty_output><jupyter_text>Let us check this for the first 30 values:<jupyter_code>checks = [check_formula(K) for K in range(30)]
all(checks)  # `all` combines all booleans in a list<jupyter_output><empty_output><jupyter_text>We can then use the alternative formula to write a large file with the first 500 Fibonacci numbers:<jupyter_code>with open('fibonacci.txt', 'w') as textfile:
    for n in range(500):
        fib_number = int(round(alt_fibonacci(n), 0))  # Rounding the number
        textfile.write(str(fib_number) + "\n")  # Writing it<jupyter_output><empty_output><jupyter_text>--- ExercisesHere are a number of exercises that are possible to carry out using the code concepts discussed:- Recursion, writing code that matchs mathematical recursive definitions. For example \\(a(0)=1\\) and \\(a(n)=2a(n-1)\\):    ```python    def sequence_a(n):        if n == 0:   base case           return 1          return 2 * a(n - 1)   recursive relationship    ```- Writing to file with `open("file.txt", "w")` and reading from file with `open("file.txt", "r")` --- Exercise 1**Debugging exercise**The following is an attempt to write \\(n!\\) as a recursive function. Findand fix all the bugs.```pythondef factorial(n):    """A function that returns factorial n"""    return n * factoial(n)```<jupyter_code>def factorial(n):
    """A function that returns factorial n"""
    # Need a base case:
    if n == 0:
        return 1
    #return n * factoial(n)  # Typo in 'factorial' and not correct value.
    return n * factorial(n - 1)<jupyter_output><empty_output><jupyter_text>A quick check:<jupyter_code>for n in range(5):
    print(n, factorial(n))<jupyter_output>0 1
1 1
2 2
3 6
4 24<jupyter_text>--- Exercise 2Write a recursive function that returns the Catalan numbers \\(C(n)\\) defined by the following:1. Base case: \\(C(0)=1\\);2. Recursive rule: \\(C(n)=\sum_{i=0}^{n-1}C(i)C(n-1-i)\\)<jupyter_code>def catalan(n):
    """Returns the nth Catalan number using recursion"""
    if n == 0:
        return 1
    return sum([catalan(i) * catalan(n - i - 1) for i in range(n)])<jupyter_output><empty_output><jupyter_text>Here is the first 5 terms:<jupyter_code>for n in range(5):
    print(catalan(n))<jupyter_output>1
1
2
5
14<jupyter_text>--- Exercise 3Verify for the first 15 values of \\(n\\) that the followingalternative formula also gives the Catalan numbers (this is in fact the morecommonly used formula):\\[    C(n) = \frac{(2n)!}{(n+1)!n!}\\]Write the first 500 catalan numbers to file.You can use the factorial function we defined in this lab sheet (Exercise 1) or you   can use the `math` library: `math.factorial`.<jupyter_code>import math  # Use the factorial from the math library

def alt_catalan(n):
    """An alternative formula for the Catalan numbers"""
    return math.factorial(2 * n) / (math.factorial(n + 1) * math.factorial(n))<jupyter_output><empty_output><jupyter_text>Here is a function to check the formula:<jupyter_code>def check_formula(n):
    """
    Check the value for the nth Cataln number
    """
    return  catalan(n) == alt_catalan(n)<jupyter_output><empty_output><jupyter_text>Here we are checking the first 15 numbers:<jupyter_code>checks = [check_formula(n) for n in range(15)]
all(checks)  # `all` combines all booleans in a list<jupyter_output><empty_output><jupyter_text>---- Exercise 4The file `primes.csv` ([download](/{{root}}/nbs/chapters/primes.csv)) contains the first million prime numbers. Use it to attempt to verify [Goldbach's conjecture](https://en.wikipedia.org/wiki/Goldbach%27s_conjecture). Let us first check Goldbachs conjecture using a small list of primes.<jupyter_code>primes = [2, 3, 5, 7, 11]
def check_goldbach(n, primes):
    """
    Checks that n (if it is even) can be written as 
    the sum of two numbers in the list `primes`
    """
    if n % 2 == 1:
        # If n is odd than the conjecture is still true
        return True
    for p1 in primes:
        for p2 in primes:
            if p1 + p2 == n:
                return True, p1, p2
    # If we loop over all primes and do not obtain 
    # the required sum then the conjecture is false
    return False
check_goldbach(6, primes)
check_goldbach(10, primes)<jupyter_output><empty_output><jupyter_text>We can check a few numbers as above but after a while we won't have enough prime numbers, for example with \\(n=20\\) we get a failure:<jupyter_code>check_goldbach(20, primes)<jupyter_output><empty_output><jupyter_text>Let us read in the large number of primes:<jupyter_code>with open("primes.csv", 'r') as outfile:
    data = [int(prime) for prime in outfile.read().split()]<jupyter_output><empty_output><jupyter_text>Let us look at the last 10 entries:<jupyter_code>data[-10:]<jupyter_output><empty_output><jupyter_text>We can now confirm that \\(n=20\\) is not a counter example to Goldbach's conjecture:<jupyter_code>check_goldbach(20, data)<jupyter_output><empty_output><jupyter_text>Let us check the first 200 integers that are even:<jupyter_code>upper_count = 200
count = 0 
n = 2
bools = []
while count < upper_count:
    n += 1
    if n % 2 == 0:
        count += 1
        bools.append(check_goldbach(n, data)[0])  # Appending the first element<jupyter_output><empty_output><jupyter_text>Let us check all our booleans:<jupyter_code>all(bools), len(bools)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12342376767290791, 'fraction_numerical': 0.02111196025983951, 'mean_word_length': 4.242363545317977, 'pattern_counts': {'":': 0, '<': 102, '<?xml version=': 0, '>': 101, 'https://': 9, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '26', 'dir': 'jupyter-structured-clean-dedup', 'id': '656241', 'license': 'MIT', 'n_tokens_mistral': 3701, 'n_tokens_neox': 3479, 'n_words': 1217, 'path': 'nbs/chapters/03-Writing-to-files-and-recursion.ipynb', 'repo_name': 'geraintpalmer/cfm', 'size': '10468'}