Loops part 2, functions review, and recursion.¶

For loops complete a set of repeat instructions by stepping through a list of elements in sequential order. This is often either the elements in a list, tuple or numpy array data type. A for loop can also be set up to step through an index, where the index steps through array elements.
While loops complete a set of repeat instructions until a condition is met, based on a conditional operator like (>, <, or ==). While loops can be useful when you need to keep iterating for an unspecified number of times, until an outcome is achieved. This is helpful when it is not easy to know how many times will be required to complete the loop.
The last kind of loop is a unique programming concept called recursion. This loop takes the operation or algorithm and breaks it into a set of smaller, nested, and sometimes simpler operations. This is accomplished by allowing the function to call itself until a condition is met.

A note about functions (modules)¶

You can pass more than one variable into a function - all these values go inside the parentheses on the 'def' line:
```
def calcsomething(input1,input2,input3):
```
You can also specify the default values for an input variable. This is called overloading and it allows the user of the function to specify the input, or not.
```
def calcsomething(input1,input2,input3='yesplot')
```

When calcsomething is evaluated, it can be called several ways

I1 = 1.;  I2 = 2.; I3 = 'noplot';
calcsomething(I1,I2,I3);

calcsomething(I1,I2); #In this case, I3 will default to 'yesplot'

A function can also pass a number of variables out at the return¶

def calcsomething(input1,input,input3);
    output1 = input1+input2;
    output2 = output2/output3;
    return output1, output2

1. For loops, a review¶

We have seen how for loops can be used to step through a container object, and become each element in that container:

In [ ]:

P = 'Fruit'
for w in P:
    print(w)

We have seen for loops used with indices to sequentially index objects in a container:

In [ ]:

# PYTHON
# Looping N times to do an operation with an index

su = 0

cont = [3,3,4,4,5,4,1,2,3,6]

for i in range(10):
    #print(i)
    su+=i #Sum all instances of i.
    print(cont[i])

In [ ]:

# R
# Looping N times to do an operation with an index

su <- 0

cont = list(3,3,4,4,5,4,1,2,3,6)

for (i in 1:length(cont)) {
    su = su + i
    print(cont[i])
    }

A for loop can be used to compute the factorial operator:

$$ 5! = (5)*(4)*(3)*(2)*(1) $$$$ N! = N*(N-1)*(N-2)....(N-(N-1))$$

In [ ]:

# Algorithm to use a for loop to calculate factorial
# N! = N*(N-1)*(N-2)*(N-3)...*(N-(N-1))

# Need to loop in descending order starting from N.
# Initialize a variable (su) to hold the result of the multiplication at each step.
# Pass su forward in the loop and multiply it by the next value of (N-i), where i in (N-(N-1)).
# Use range(start,stop,step) function
# Return the result from the function/module.

# Write a for loop to compute the factorial

def forfakt(N):
    # initialize 
    su = N;
    for ni in range(N-1,0,-1): # The Range function can take inputs start,stop,step
        su *= ni;
    return su
            
forfakt(3)

2. While loops¶

While loops are helpful when it's not easy to predict how many iterations are required to reach the end point. They can be used to iterate an unspecified number of times until a solution converges or to break up an array into an unknown number of chunks, based on some criteria.

In [ ]:

# Python
# Write an algorithm to compute the factorial with a while loop.
def whilefakt(N):   
    # initialize an index
    idx = 0;
    fakt = 1;
    while idx < N:
        fakt *= (N-idx);
        idx += 1  #increment idx.      
    return fakt

whilefakt(3)

In [ ]:

# R
# Write an algorithm to compute the factorial with a while loop.
whilefakt <- function(N) {
  idx <- 0
  fakt <- 1
  while (idx < N) {
    fakt <- fakt * (N - idx)
    idx <- idx + 1
  }
  return(fakt)
}

whilefakt(3)

While loops are an effective way to do fixed-point iteration.¶

Fixed point iteration is a way to solve algebraic functions where the unknown can't be isolated, such as rood-finding of quadratic equations.

One approach is to use Newton's Fixed-point iteration solver: $$ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} $$

This can be applied to e.g. find the roots of a quadratic equation, although there can be some limits on convergence.

An example from chemistry is the solution to the carbonate system equation, in terms of hydrogen ions [H+]

$$ \frac{K_0K_1pCO_2}{[H+]}+2\frac{K_0 K_1 K_2pCO_2}{[H+]^2}+\frac{K_w}{[H+]}+\frac{TB K_B S}{[K_B H+]}- ALK = 0 $$

Here, all terms are constant except hydrogen ion, but hydrogen ion is not separable from the rest of the equation, so we must use root finding or fixed-point iteration to determine the solution.

In [ ]:

# Find a root of the equation x^3+2x+1, using Newton's method.
# Algorithm:
# Specify an initial value for x.  
# Evaluate x_n+1 = x_n -....  at each step.

# f(x) = x^3+2x+1
# f'(x) = 3x^2 + 2
# 

import numpy as np
import matplotlib.pyplot as plt

x = 100; # initial guess for x
Dx = 10; # initial value for 
plt.figure(); plt.grid('on');
j=0

Err = 2e-7

while np.abs(Dx) > Err:
    
    fx = x**3 + 2*x + 1
    dx = 3*x**2 + 2
    xi = x - fx/dx
    # plt.plot(j,xi,'.'); plt.ylabel('$x_i$'); plt.xlabel('iteration')
    plt.plot(j,Dx,'.'); plt.ylabel('$Dx_i$'); plt.xlabel('iteration')
    
    # compute Dx
    Dx = (xi - x)
    
    x = xi
    j+=1
    
print(x)

In [ ]:

3. Recursive functions loop by calling themselves and breaking down the problem into sub-problems¶

Source: The Matryoshka dolls capture the heuristic of of a recursive operation. At each iteration, the next doll is opened to reveal a new, smaller problem whos solution completes the set.

Here is an example of a recursive bedtime story, adapted from this stackoverflow article.

A child couldn't sleep, so her mother told her a story about a little frog who couldn't sleep, 
    and in that story, the frog's mother told her a story about a little bear who couldn't sleep, 
        and in that story, the bear's mother told her a story about a little weasel... 
            who fell asleep.
         ...and then the little bear fell asleep;
    ...and then the little frog fell asleep;
...and finally, the child fell asleep.

In [ ]:

I use recursion to step through an unknown number of chromatogram peaks and identify when the peak started and returned to the baseline. After each peak is identified, the remaining fragment of the chromatogram is passed forward into the recursive function, so no peak is counted twice.¶

In [ ]:

# Python 
# Algorithm for printing a word in reverse order, using recursion in Python:
#
# 1. Check that we received a word or object that is not empty.
# 2. Print the last letter in the word,
# 3. Send the remainder of the word fragment to the module backwords (the recursion).
# 4. If the check in step 1 is false, it means we're finished. Print the first letter and return without a call to the same function.


# Recursion to say a word backward.
    
word = 'homeontherange';

def backwords(word):
    
    if len(word) > 1:
        # This is the recursion line; the function returns a call to itself.
        # Note, Python lets you use the '+' symbol to combine characters into a string.
        return word[-1] + backwords(word[:-1])
    else:
        # This is the exit sequence: When only the first letter is left, return that and don't call yourself.
        return word[0] 
    
bakw = bwords(word)
print(bakw)

In [ ]:

print('a'+'b'+'c')

In [ ]:

# Python
# Algorithm to compute factorials by recursion.
# Enter the function
# Subtract 1 from N and perhaps save as variable.
# Take product of N with N-1
# Need to be able to use the output from the function as a term in the product or sum.

def recmath(N):
    if N > 1:
        return N*recmath(N-1)
    else: 
        return 1
    
recmath(3)

In [ ]:

# R
# Algorithm to compute factorials by recursion.
# Enter the function
# Subtract 1 from N and perhaps save as variable.
# Take product of N with N-1
# Need to be able to use the output from the function as a term in the product or sum.

recmath <- function(N) {
  if (N > 1) {
    return(N * recmath(N - 1))
  } else {
    return(1)
  }
}

recmath(3)

Complete the exercises below and submit.¶

Fibonacci sequence¶

A Fibonacci sequence starts with 0 and 1 and every number that follows is the sum of the previous two numbers, e.g.:

$$ F_1 = 0, \; F_2 = 1. $$$$ F_n = F_{n-1}+F_{n-2} $$

Your instructions: Write an algorithm and a function (module) to determine the Fibonacci sequence, given N, the number of elements, and by specifying the first values in the sequence as 0 and 1. ** Solve the exercise 3 ways:

Using a for loop.
Using a while loop.
Using recursion.

In [ ]:

# --------- Write an Algorithm to determine fibonacci sequence, given how many numbers to include in the sequence.
# Let N be 

# --------- Write code to determine the fibonacci sequence using a for loop, given your algorithm.

In [ ]:

# --------- Write an Algorithm to determine fibonacci sequence, given how many numbers to include in the sequence.

# --------- Write code to determine the fibonacci sequence using a while loop, given your algorithm.

In [ ]:

# --------- Write an Algorithm to determine fibonacci sequence, given how many numbers to include in the sequence.

# --------- Write code to determine the fibonacci sequence using recursion, given your algorithm.