1 Recursion

#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
Exponentiation
"""

print(2**8)


# %% Loop
def exp_loop(b: int, n: int) -> int:
    result = 1
    for c in range(n):
        result *= b
        print("c=", c, "and result=", result)
    return result


for n in range(1, 17):
    val = exp_loop(2, n)
    print("2 to the ", n, "is ", val, "\n")


# %% What is the b^-n?
def exp_loop_neg_rec(b: int, n: int) -> float:
    result = 1
    if 0 <= n:
        for c in range(n):
            result *= b
            print("c=", c, "and result=", result)
        return result
    else:
        return 1 / exp_loop_neg_rec(b, -n)


for n in range(-1, -17, -1):
    val_float = exp_loop_neg_rec(2, n)
    print("2 to the ", n, "is ", val_float, "\n")


# %% Inefficient recursive exponentiation
def exp_rec(b: int, n: int) -> int:
    """
    Calculates b^n for positive n integers
    """
    print("Calling with b =", b, "and n=", n)
    if n == 0:
        return 1
    else:
        return b * exp_rec(b, n - 1)


for n in range(1, 17):
    val = exp_rec(2, n)
    print("2 to the ", n, "is ", val, "\n")


# %% Efficient recursive exponentiation
def exp_rec_eff(b: int, n: int) -> int:
    """
    Efficiently calculates b^n for positive n integers
    """
    print("Calling with b =", b, "and n=", n)
    if n == 1:
        return b
    elif (n & 1) == 0:
        return exp_rec_eff(b * b, n // 2)
    else:
        return exp_rec_eff(b * b, n // 2) * b


for n in range(1, 17):
    val = exp_rec_eff(2, n)
    print("2 to the ", n, "is ", val, "\n")

/**
Functions to take exponents: b^n
Note: ^ is not c++ syntax for exponentiation.
**/

#include <iostream>
#include <exception>
using namespace std;

// With a loop, accumulating up
double simpleExpLoopPart(int b, int n) {
  double result = 1;

  for (int c = 1; c <= n; c++) {
    result *= b;
    cout << "c = " << c << ", and result = " << result << endl;
  }

  return result;
}; // what will happen if we enter a negative number? What about 0?

// With a loop and one-layer recursion for negatives
double simpleExpLoop(int b, int n) {
  double result = 1;

  if (n >= 0) {
    for (int c = 1; c <= n; c++) {
      result *= b;
      cout << "c = " << c << ", and result = " << result << endl;
    }
  } else {
    return 1 / simpleExpLoop(b, -n);
  }

  return result;
};

// Fully recursively no negatives
double simpleExpRecurPart(int b, int n) {
  cout << "Calling simpleExpRecurPart with b = " << b << " and n = " << n
       << endl;

  if (n == 0) {
    return 1;
  } else {
    return b * simpleExpRecurPart(b, n - 1);
  }

  // can have return statements above or 1 here
} // what will happen if we enter a negative number?

// Fully ecursively:
double simpleExpRecur(int b, int n) {
  double result = 1;

  cout << "Calling simpleExpRecur with b = " << b << " and n = " << n << endl;

  if (n == 0) {
    return 1;
  } else if (n > 0) {
    return b * simpleExpRecur(b, n - 1);
  } else {
    return 1 / simpleExpRecur(b, -n);
  }

  // can have return statements above or 1 here
}

// Fast exponentiation (skipped 0^neg and negative special conditions here)
long long expEff(const long long b, const int n) {
  cout << "Calling expEff with b = " << b << " and n = " << n << endl;
  if (n == 1) {
    // this is a faster alternative to base case n==0 above, how much?
    return b;
  } else if ((n & 1) == 0) {
    // bitwise faster than modulus to check even here
    return expEff(b * b, n / 2);
  } else {
    // odd
    return expEff(b * b, n / 2) * b;
  }
  // can have return statements above or 1 here
}

int main() {
  int b = 2;
  int n = 40;

  cout << "simpleExpLoopPart: " << simpleExpLoopPart(b, n) << endl << endl;
  cout << "simpleExpLoop: " << simpleExpLoop(b, n) << endl << endl;
  cout << "simpleExpRecurPart: " << simpleExpRecurPart(b, n) << endl << endl;
  cout << "simpleExpRecur: " << simpleExpRecur(b, n) << endl << endl;
  cout << "expEff: " << expEff(b, n) << endl << endl;

  return 0;
}

#!/usr/bin/runghc

module AlgExp where

import Data.Bits

-- |
-- >>> expFun 2 3
-- 8
expFun :: Integer -> Int -> Integer
expFun b n = product (replicate n b)

-- |
-- >>> expRec 2 3
-- 8 % 1
expRec :: Rational -> Integer -> Rational
expRec b n
  | n == 0 = 1
  | 0 < n = b * expRec b (n - 1)
  | otherwise = 1 / expRec b (-n)

-- |
-- >>> expEff 2 3
-- 8
expEff :: Integer -> Integer -> Integer
expEff b n
  | n == 1 = b
  | n .&. 1 == 0 = expEff (b * b) (div n 2)
  | otherwise = b * expEff (b * b) (div n 2)

main :: IO ()
main = do
  print (expRec 2 3)
  print (expFun 2 3)
  print (expEff 2 3)

#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
Order of statements in the stack matters.

Note, this string defaulted-tab trick is handy!
This program counts from 4, with tabs
"""


def order_matters(n: int, indent: str = "    ") -> None:
    print("\n", indent, " Next call starts here", sep="")
    print(indent, "Before the recursive call, n is", n)
    if n > 0:
        print(indent, "calling with ", n + 1)
        order_matters(n - 1, indent + "    ")
    print(indent, "After the recursive call, n is ", n, "\n")
    print(indent, "Function call ends here")


order_matters(4)

/**
Illustrates printing before and after a recursive call.
**/

#include <iostream>
using namespace std;

void orderMatters(int c, string indent = "") {
  cout << indent << "c before the recursive statement: " << c << endl;
  if (c > 0) {
    orderMatters(c - 1, indent += " ");
  }
  // This statement will not show up if you returned countdown's value
  cout << indent << "c after the recursive statement: " << c << endl;
}

int main() {
  orderMatters(4);
  return 0;
}

/**
Become a recursion superstar...
**/

#include <iostream>
using namespace std;

void stars(int n, string indent = "") {
  cout << indent << " Before with n=" << n << endl;
  if (n > 1) {
    stars(n - 1, indent += "*");
    cout << indent << " After with n=" << n << endl;
  }
  return;
}

void starsPlus(int n, string indent = "") {
  cout << indent << " Before with n=" << n << endl;
  if (n > 1) {
    stars(n - 1, indent + "*");
    cout << indent << " After with n=" << n << endl;
  }
  return;
}

int main() {
  int n;
  cout << "Enter a depth: ";
  cin >> n;
  stars(n);
  cout << endl << endl;
  starsPlus(n);
  return 0;
}

#!/usr/bin/runghc

module Recursion01OrderMatters where

orderMatters :: Int -> String -> String
orderMatters n indent =
  if n > 0
    then show n ++ indent ++ "before\n" ++ orderMatters (n - 1) (indent ++ "  ") ++ show n ++ indent ++ "after\n"
    else ""

main :: IO ()
main = do
  putStrLn (orderMatters 4 " ")

#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
Factorial.
For example, factioral(5) is:
5! = 5 * 4 * 3 * 2 * 1
"""

import math

print(math.factorial(5))


# %% Recursive
def factorial_rec(n: int) -> int:
    "Computes n! for positive n integers"
    if n == 0:
        return 1
    else:
        return n * factorial_rec(n - 1)


for n in range(1, 11):
    val = factorial_rec(n)
    print(n, " factorial is ", val)

/**
Various implementations of factorial.
**/

#include <iostream>
#include "astack.h"
#include <exception>
using namespace std;

double factorial(int n, string indent = "") {
  double result;
  cout << indent << "Calling factorial with n = " << n << endl;
  if (n > 1) {
    // can just return instead if you don't want fancy print immediately below
    result = n * factorial(n - 1, indent += " ");
    cout << indent << "Unwinding factorial with n = " << n
         << ",  and result = " << result << endl;
  } else if (n < 0) // undefined
  {
    throw exception();
  } else {
    result = 1;
  }
  return result;
}

double factorialTail(int n, int sum = 1, string indent = "") {
  cout << indent << "Calling factorial with n = " << n << " and sum = " << sum
       << endl;
  // error condition
  if (n < 0) {
    throw exception();
  } else if (1 == n) {
    return sum;
  }
  // Tail recursive call
  return factorialTail(n - 1, n * sum, indent += " ");
  // We can't cout anything on the way back up the stack
}

// Iterative Factorial using loops (imperative), accumulate pattern
double factorialLoop(int n) {
  double total = 1;
  for (int i = 1; i < n + 1; i++) {
    total *= i;
    cout << "FactLoop n = " << n << " and i = " << i << " and total = " << total
         << endl;
  }
  return total;
}

// three outside variables are referenced by the loop: total, i, and n

// Loop turned into a tail recursive function
double factLoopRec(int n, double total = 1, int i = 1) {
  cout << "FactTail2 n = " << n << " and i = " << i << " and total = " << total
       << endl;
  if (i < (n + 1))
    return factLoopRec(n, total * i, i + 1);
  else
    return total;
}

// replacing recursion with a stack (uses stack class above)
// We'll cover this later
long long factStack(int n, Stack<double> &S) {
  while (n > 1) {
    S.push(n--);
  }
  long long result = 1;
  while (S.length() > 0) {
    cout << "factStack n = " << n << " and result = " << result << endl;
    result = result * S.pop();
  }
  return result;
}

int main() {
  int n;
  cout << "Enter a number to find factorial: ";
  cin >> n;
  cout << "Factorial middle recursive: " << n << " = " << factorial(n) << endl
       << endl;
  cout << "Factorial tail recursive: " << n << " = " << factorialTail(n) << endl
       << endl;
  cout << "Factorial loop: " << n << " = " << factorialLoop(n) << endl << endl;
  cout << "Factorial factLoopRec: " << n << " = " << factLoopRec(n) << endl
       << endl;
  AStack<double> stk(50);
  cout << "Factorial factStack: " << n << " = " << factStack(n, stk) << endl
       << endl;
  return 0;
}

#!/usr/bin/runghc

module Recursion02Factorial where

import Data.List

-- Four different versions of Factorial(n):

factInf :: Int -> Integer
factInf n = product (take n [1 ..])

factRec :: Integer -> Integer
factRec 0 = 1
factRec n = n * factRec (n - 1)

factTail :: Integer -> Integer -> Integer
factTail 0 sum = sum
factTail n sum = factTail (n - 1) (n * sum)

factFoldl :: Integer -> Integer
factFoldl n = foldl' (*) 1 [1 .. n]

main :: IO ()
main = do
  print (factInf 5)
  print (factInf 10)

  print (factRec 5)
  print (factRec 10)

  print (factTail 5 1)
  print (factTail 10 1)

  print (factFoldl 5)
  print (factFoldl 10)

#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
Created on Sat Dec 3 18:16:57 2016
@author: taylor@mst.edu
Recursion is the bomb!
"""


def recursion_lecture(day: int) -> None:
    print("Learning recursion", day)
    return recursion_lecture(day + 1)


day = 0
recursion_lecture(day)

#!/usr/bin/runghc

module Recursion03Bomb where

recursionLecture :: Int -> String -> String
recursionLecture day indent = indent ++ " More recursion\n" ++ recursionLecture (day + 1) (indent ++ "  ")

main :: IO ()
main = do
  putStrLn (take 500 (recursionLecture 0 ""))

#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
Created on Sat Dec 3 18:16:57 2016
@author: taylor@mst.edu
"""


def is_even(no: int) -> bool:
    print("Calling isOdd with: ", no)
    if 0 == no:
        return True
    else:
        return is_odd(no - 1)


def is_odd(no: int) -> bool:
    print("Calling isOdd with: ", no)
    if 0 == no:
        return False
    else:
        return is_even(no - 1)


for n in range(10):
    # OK but comprehensible way to detect even/odd
    if n % 2 == 0:
        print(n, "is even")
    else:
        print(n, "is odd")

    # Fastest way with bitwise operator
    # (just & with last bit, not whole number division)
    if n & 1 == 0:
        print(n, "is even")
    else:
        print(n, "is odd")

    # A terribly ineffecient way to detect even/odd
    if is_even(n):
        print(n, "is even")
    else:
        print(n, "is odd")

/**
Mutual recursion
**/

#include <iostream>
using namespace std;

bool isOdd(int no);

bool isEven(int no) {
  cout << "Calling isEven with: " << no << endl;
  if (0 == no)
    return true;
  else
    return isOdd(no - 1);
}

bool isOdd(int no) {
  cout << "Calling isOdd with: " << no << endl;
  if (0 == no)
    return false;
  else
    return isEven(no - 1);
}

int main() {
  int number;
  cout << "Input an integer" << endl;
  cin >> number;
  if (isEven(number))
    cout << "Your number is even" << endl;
  else
    cout << "Your number is odd" << endl;
  return 0;
}

#!/usr/bin/runghc

module Recursion04EvenOdd where

import Data.Bits

isEven :: Int -> Bool
isEven 0 = True
isEven n = isOdd (n - 1)

isOdd :: Int -> Bool
isOdd 0 = False
isOdd n = isEven (n - 1)

main :: IO ()
main = do
  putStrLn "Slowest:"
  print (isEven 10)
  print (isEven 5)
  print (isOdd 10)
  print (isOdd 5)

  putStrLn "\nLess slow:"
  print (mod 10 2 == 0)
  print (mod 5 2 == 0)
  print (mod 10 2 /= 0)
  print (mod 5 2 /= 0)

  putStrLn "\nFastest:"
  print ((10 :: Int) .&. 1 == 0)
  print ((5 :: Int) .&. 1 == 0)
  print ((10 :: Int) .&. 1 /= 0)
  print ((5 :: Int) .&. 1 /= 0)

  putStrLn "\nBuilt in:"
  print (even 10)
  print (even 5)
  print (odd 10)
  print (odd 5)

#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
Word reversal.
"""

# Basic iterable reversal:
"astr"[::-1]

# reversed function
"".join(list(reversed("astr")))

# reversed with list comp
"".join([char for char in reversed("astr")])

# Manually with a loop:
mystr = "astr"
accumstring = ""
for ichar in range(len(mystr) - 1, -1, -1):
    accumstring += mystr[ichar]


# %% Simple string reversal
def reverse_me(s: str) -> str:
    "Reverses a string, and returns nothing."
    if s == "":
        return s
    else:
        return reverse_me(s[1:]) + s[0]


print("Enter something you'd like backwards:")
print(reverse_me("taxes"))


# %% Simple string reversal with tab trick
def reverse_me_indent(s: str, indent: str = "    ") -> str:
    "Reverses a string, and returns nothing."
    print(indent, "Starting another call with:", s)
    if s == "":
        return s
    else:
        return reverse_me_indent(s[1:], indent + "    ") + s[0]


print("\nEnter something you'd like backwards:")
print(reverse_me_indent("evil"))

/**
Simple word reversal
**/

#include <iostream>
using namespace std;

void reverseMe() {
  char ch;
  cin.get(ch);

  if (ch != '\n') {
    reverseMe();

    cout.put(ch); // after recursive statement means what?
  }
}

int main() {
  cout << "Enter something you would like backwards: ";
  // how about taxes?

  reverseMe();

  return 0;
}

#!/usr/bin/runghc

module Recursion05Reverse where

import Data.List

-- This one is inefficient
reverseMe :: [a] -> [a]
reverseMe [] = []
reverseMe (x : xs) = reverseMe xs ++ [x]

reverseEff :: [a] -> [a] -> [a]
reverseEff [] new = new
reverseEff (x : xs) new = reverseEff xs (x : new)

reverseFoldl :: [a] -> [a]
reverseFoldl = foldl' (\acc x -> x : acc) []

reverseFlip :: [a] -> [a]
reverseFlip = foldl' (flip (:)) []

main :: IO ()
main = do
  putStrLn (reverse "evil")
  putStrLn (reverseMe "taxes")
  putStrLn (reverseEff "backwards" [])
  putStrLn (reverseFoldl "reverse")
  putStrLn (reverseFlip "park")

-- boobytrap

#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
Recursive palindrome
"""


def is_palindrome_rec(s: str) -> bool:
    "Returns True if s is a palindrome and False otherwise."
    if len(s) <= 1:
        return True
    else:
        return s[0] == s[-1] and is_palindrome_rec(s[1:-1])


print(is_palindrome_rec("racecar"))
# Quitting early?
print(is_palindrome_rec("racecat"))
print(is_palindrome_rec("able was I ere I saw elba"))


# %% Recursive palindrome with better output
def is_palindrome_rec_out(s: str, indent: str = "    ") -> bool:
    """
    Returns True if s is a palindrome and False otherwise,
    With nice stack illustration.
    """
    print(indent, "called with: ", s)
    if len(s) <= 1:
        print(indent, "base case")
        return True
    else:
        ans = s[0] == s[-1] and is_palindrome_rec_out(s[1:-1], indent + "    ")
        print(indent, "About to return: ", ans)
        return ans


# Note: This algorithm handles odd and even strings just fine
# (think about base case)
print(is_palindrome_rec_out("racecar"))
print(is_palindrome_rec_out("racecat"))
print(is_palindrome_rec_out("tacocat"))
print(is_palindrome_rec_out("anutforajaroftuna"))
print(is_palindrome_rec_out("able was I ere I saw elba"))
print(is_palindrome_rec_out("neveroddoreven"))
# https://www.grammarly.com/blog/16-surprisingly-funny-palindromes/

/**
Palindrome detector

Examples:
able was i ere i saw elba
racecar
**/

#include <iostream>
#include <string>
using namespace std;

bool isPalindrome(string input, string indent = "") {
  bool result;
  string in = input;
  cout << indent << in << endl;
  // why don't we use == 1 ?
  if (in.length() <= 1) {
    result = true;
  } else {
    // what happens for an almost palindrome (middle mismatch)
    result = ((in[0] == in[in.length() - 1]) &&
              isPalindrome(input.substr(1, in.length() - 2), indent += " "));
    cout << indent << in << endl;
  }
  return result;
}

int main() {
  cout << "Enter a palindrome: " << endl;
  string input;
  getline(cin, input);
  if (isPalindrome(input)) {
    cout << "That is a palindrome" << endl;
  } else {
    cout << "That is NOT a palindrome" << endl;
  }
  return 0;
}

#!/usr/bin/runghc

module Recursion06IsPalindrome where

import Data.List as L
import Data.Vector as V

isPalindromeRev :: (Eq a) => [a] -> Bool
isPalindromeRev xs = xs == L.reverse xs

isPalindromeRec :: (Eq a, Show a) => Vector a -> Bool
isPalindromeRec xs =
  V.length xs == 1
    || let lastPos = (V.length xs - 1)
           firstElem = xs V.! 0
           lastElem = xs V.! lastPos
        in firstElem == lastElem && isPalindromeRec (V.slice 1 (lastPos - 1) xs)

main :: IO ()
main = do
  print (isPalindromeRev "a")
  print (isPalindromeRev "racecar")
  print (isPalindromeRev "racecat")
  print (isPalindromeRec (V.fromList "a"))
  print (isPalindromeRec (V.fromList "racecar"))
  print (isPalindromeRec (V.fromList "racecat"))

#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
Greatest Common Divisor using Euclid's Algorithm
"""


# %% GCD  loop
def gcd_loop(a: int, b: int) -> int:
    "Return the Greatest Common Divisor of a and b using Euclid's Algorithm"
    while a != 0:
        a, b = b % a, a
    return b


print(gcd_loop(10, 15))


# %% CGD recursive
def gcd_rec(a: int, b: int) -> int:
    "Return the Greatest Common Divisor of a and b using Euclid's Algorithm"
    if b == 0:
        return a
    else:
        return gcd_rec(b, a % b)


print("The GCD of 10 and 15 is:")
print(gcd_rec(10, 15))

/**
GCD using both a loop and recursion.
**/

#include <iostream>
using namespace std;

// Euclid's non-recursive method for GCD:
long long gcdLoop(long long dividend, long long divisor) {
  while (divisor != 0) {
    long long remainder = dividend % divisor;
    cout << "Dividend = " << dividend << ", divisor = " << divisor
         << ", remainder =" << remainder << endl;
    dividend = divisor;
    divisor = remainder;
  }

  return dividend;
}

// Tail Recursive GCD
long long gcdRec(const long long dividend, const long long divisor) {
  long long remainder = dividend % divisor;
  cout << "Dividend = " << dividend << ", divisor = " << divisor
       << ", remainder =" << remainder << endl;
  if (remainder == 0)
    return divisor;
  else
    return gcdRec(divisor, remainder);
}

int main() {
  cout << "gcdLoop: " << gcdLoop(24212, 238) << endl << endl;
  cout << "gcdRec: " << gcdRec(24212, 238) << endl << endl;

  return 0;
}

module CryptoMath where

-- |
-- >>> gcd' 55 30
-- 5
gcd' :: Int -> Int -> Int
gcd' a b =
  if mod a b == 0
    then b
    else gcd' b (mod a b)

-- |
-- >>> modInv 5 66
-- Just 53

-- |
-- >>> modInv 6 66
-- Nothing
modInv :: Int -> Int -> Maybe Int
modInv a m
  | 1 == g = Just (mkPos i)
  | otherwise = Nothing
  where
    (i, _, g) = gcdExt a m
    mkPos x
      | x < 0 = x + m
      | otherwise = x

-- Extended Euclidean algorithm.
-- Given non-negative a and b, return x, y and g
-- such that ax + by = g, where g = gcd(a,b).
-- Note that x or y may be negative.
gcdExt :: Int -> Int -> (Int, Int, Int)
gcdExt a 0 = (1, 0, a)
gcdExt a b =
  let (q, r) = quotRem a b
      (s, t, g) = gcdExt b r
   in (t, s - q * t, g)

#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
Sum more recursion...
"""


# %% Sum Iterative
def sum_loop(my_list: list[int]) -> int:
    "Iterative sum"
    accum_sum = 0
    # Add every number in the list.
    for i in range(0, len(my_list)):
        accum_sum = accum_sum + my_list[i]
    # Return the sum.
    return accum_sum


print(sum_loop([5, 7, 3, 8, 10]))


# %% Sum Recursive
def sum_rec(my_list: list[int]) -> int:
    "Recursive sum"
    if len(my_list) == 1:
        return my_list[0]
    else:
        return my_list[0] + sum_rec(my_list[1:])


print(sum_rec([5, 7, 3, 8, 10]))


# %% count/length Recursive
def count_rec(my_list: list[int]) -> int:
    "Recursive count/length"
    if len(my_list) == 1:
        return 1
    else:
        return 1 + count_rec(my_list[1:])


print(count_rec([5, 7, 3, 8, 10]))

#!/usr/bin/runghc

module Recursion08SumCount where

sumRec :: (Num a) => [a] -> a
sumRec [] = 0
sumRec (x : xs) = x + sumRec xs

sumFld :: (Num a) => [a] -> a
sumFld xs = foldr (+) 0 xs

cntRec :: (Num a) => [a] -> a
cntRec [] = 0
cntRec (_ : xs) = 1 + cntRec xs

main :: IO ()
main = do
  print (sum [1 .. 10])
  print (sumRec [1 .. 10])
  print (sumFld [1 .. 10])

  print (length [1 .. 10])
  print (cntRec [1 .. 10])

#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
Efficiency discusion using fibonacci sequence:

f(n) = f(n - 2) + f(n - 1)
     = 1 if n == 0 or n == 1
"""


# fibonacci using a loop
def fib_loop(n: int) -> int:
    "Computes first n fib numbers, using loop"
    a, b = 0, 1  # the first and second Fibonacci numbers
    for i in range(n):
        a, b = b, a + b
    return a


print(fib_loop(10))


# recursive Fibonacci (inefficient)
def fib_rec(n: int) -> int:
    """Return Fibonacci of x, where x is a non-negative int"""
    if n < 2:
        return n  # or 1
    else:
        return fib_rec(n - 1) + fib_rec(n - 2)


print(fib_rec(10))

# %% Tail recursion


# %% tail recursive fibonacci (efficient)
def fib_rec_tail(n: int, previous: int = 0, current: int = 1, i: int = 0) -> int:
    """
    Computes first n fib numbers, using tail recursion
    Another way of defaulting values.
    This is both more sensible and more dangerous,
    since the user can break it.
    """
    if i < n:
        return fib_rec_tail(n, current, previous + current, i + 1)
    else:
        return previous


print(fib_rec_tail(10))


# %% tail recursive fibonacci (efficient)
def fib_rec_tail_wrapped(n: int) -> int:
    """
    Computes first n fib numbers, using tail recursion
    One way of defaulting values, which hides the values.
    """

    def go(previous: int, current: int, i: int) -> int:
        if i < n:
            return go(current, previous + current, i + 1)
        else:
            return previous

    return go(0, 1, 0)


print(fib_rec_tail_wrapped(10))

/**
Fibonacci
f(n) = f(n-2) + f(n-1)
     = 0 or 1 if n == 0 or n == 1
**/

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// recursive Fibonacci (inefficient)
double fibonacci(int n) {
  if (n == 0)
    return 0;
  else if (n == 1)
    return 1;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

double fibonacci2(int n) {
  if (n < 2)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// fibonacci using a loop (efficient)
double fibonacciLoop(int n) {
  int i;               // the loop variable
  double previous = 0; // the first Fibonacci number
  double current = 1;  // the second Fibonacci number
  // n steps
  for (i = 0; i < n; ++i) {
    double temp = previous + current;
    previous = current;
    current = temp;
  }
  return previous;
}

// fib loop converted to tail recursive, is efficient
double fibConvert(int n, double previous = 0, double current = 1, int i = 0) {
  if (i < n)
    return fibConvert(n, current, previous + current, i + 1);
  else
    return previous;
}

// Global cache...
int fibo_cache[100] = {0};
// this batch array initialization syntax only works for 0s

// memoization/caching improves efficiency
double fibonacciCached(int n) {
  if (fibo_cache[n] == 0) {
    if (n < 2) {
      fibo_cache[n] = n;
      return n;
    } else {
      fibo_cache[n] = fibonacciCached(n - 1) + fibonacciCached(n - 2);
    }
  }
  return fibo_cache[n];
}

int main() {
  for (int i = 1; i < 44; i++)
    cout << "FibRec of " << i << " = " << fibonacci(i) << endl;
  for (int i = 1; i < 44; i++)
    cout << "FibLoop of " << i << " = " << fibonacciLoop(i) << endl;
  for (int i = 1; i < 44; i++)
    cout << "fibConvert of " << i << " = " << fibConvert(i) << endl;
  for (int i = 0; i < 30; i++)
    cout << fibo_cache[i] << ", ";
  for (double i = 1; i < 44; i++)
    cout << "fibonacciCached of " << i << " = " << fibonacciCached(i) << endl;
  return 0;
}

#!/usr/bin/runghc

module Recursion09Fibonacci where

-- This version is not efficient.
-- It re-computes values it already computed
fibRec :: Int -> Integer
fibRec 0 = 0
fibRec 1 = 1
fibRec n = fibRec (n - 1) + fibRec (n - 2)

-- The versions below are efficient:

fibTail :: Integer -> Integer -> Integer -> Integer -> Integer
fibTail n previous current i
  | i < n = fibTail n current (previous + current) (i + 1)
  | otherwise = previous

fibWrapExternal :: Integer -> Integer
fibWrapExternal n = fibTail n 0 1 0

fibWrapInternal :: Integer -> Integer
fibWrapInternal n =
  let go n previous current i =
        if i < n
          then fibTail n current (previous + current) (i + 1)
          else previous
   in go 10 0 1 0

main :: IO ()
main = do
  print (fibRec 10)
  print (fibTail 10 0 1 0)
  print (fibWrapExternal 10)
  print (fibWrapInternal 10)

#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
Created on Sat Dec 3 18:16:57 2016
@author: taylor@mst.edu
"""


# %% Iterative Factorial using loops (imperative), accumulate pattern
def fact_loop(n: int) -> int:
    "Computes the factorial of n, returns n."
    total = 1
    for i in range(1, n + 1):
        total *= i
    return total


print(fact_loop(5))


# %% tail recursive factorial
def fact_rec_tail(n: int) -> int:
    """
    Computes the factorial of n, returns n.
    One way of defaulting value, which hides the details.
    """

    def loop(total: int, i: int) -> int:
        if i < n + 1:
            return loop(total * i, i + 1)
        else:
            return total

    return loop(1, 1)


print(fact_rec_tail(5))


# %% tail recursive factorial
def fact_rec_tail2(n: int, total: int = 1, i: int = 1) -> int:
    """
    Computes the factorial of n, returns n.
    Another way of defaulting values.
    """
    if i < n + 1:
        return fact_rec_tail2(n, total * i, i + 1)
    else:
        return total


print(fact_rec_tail2(5))

#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
Countdown
"""


# %% Countdown loop
def countdown_for_loop(i: int) -> None:
    "countdown from i using iteration"
    for counter in range(i, 0, -1):
        print(counter, "    ")


countdown_for_loop(5)


# %% Countdown tail
def countdown_tail(i: int) -> None:
    "countdown from i using recursion"

    def loop(counter: int) -> None:
        if 0 < counter:
            print(counter, "    ")
            loop(counter - 1)

    loop(i)


countdown_tail(5)


# %% Countdown loop
def countdown_while_loop(i: int) -> None:
    "countdown from i using iteration"
    while 0 < i:
        print(i, "    ")
        i -= 1


countdown_while_loop(5)


# %% Countdown tail
def countdown_tail_natural(i: int) -> None:
    if i > 0:
        print(i, "    ")
        countdown_tail_natural(i - 1)


countdown_tail_natural(5)


"""
Concluding remarks:

Unfortunately, Python is not a good language in this regard.
When the value of a recursive call is immediately returned
(i.e., not combined with some other value),
a function is said to be tail recursive.
The Haskell, Scheme, Clojure programming languages optimize tail recursive functions,
so that they are just as efficient as loops both in time and in space utilization.
"""

#!/usr/bin/runghc

module Recursion11Countdown where

countDown :: Int -> String
countDown 0 = "\n"
countDown n = show n ++ "\n" ++ countDown (n - 1)

countDownTabbed :: Int -> String -> String
countDownTabbed 0 indent = indent ++ "\n"
countDownTabbed n indent = indent ++ show n ++ "\n" ++ countDownTabbed (n - 1) (indent ++ "  ") ++ indent ++ "after\n"

main :: IO ()
main = do
  putStrLn (countDown 10)
  putStrLn (countDownTabbed 10 "")

#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
Created on Sat Dec 3 18:16:57 2016
@author: taylor@mst.edu
"""

from functools import lru_cache
from typing import Optional


# %% Recall, fib is slow with recursion
# memoization specific to the problem is a fix
def fib_memo(n: int, memo: dict[int, int]) -> int:
    """
    Computes the first n fib numbers.
    """
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]


memo: dict[int, int] = {0: 0, 1: 1}
print(fib_memo(35, memo))


# %% memoizatino v2 (general)
def fib_memo_gen(n: int, fib_cache: Optional[dict[int, int]] = None) -> int:
    """
    Return Fibonacci of x, where x is a non-negative int
    Hides the memoiziation from the user!
    """
    if fib_cache is None:
        fib_cache = {}
    if n in fib_cache:
        return fib_cache[n]
    if n < 2:
        return n  # or 1
    else:
        value = fib_memo_gen(n - 1, fib_cache) + fib_memo_gen(n - 2, fib_cache)
        fib_cache[n] = value
    return value


print(fib_memo_gen(35))


# %% memoization v3 (Python general)
@lru_cache(maxsize=1000)
def fib_memo_lru(n: int) -> int:
    """
    Return Fibonacci of x, where x is a non-negative int
    Uses a decorator memoization method
    """
    if n < 2:
        return n  # or 1
    else:
        return fib_memo_lru(n - 1) + fib_memo_lru(n - 2)


print(fib_memo_lru(35))

#!/usr/bin/runghc

module Recursion12Memoization where

slowFib :: Int -> Integer
slowFib 0 = 0
slowFib 1 = 1
slowFib n = slowFib (n - 2) + slowFib (n - 1)

memoizedFib :: Int -> Integer
memoizedFib =
  let fib 0 = 0
      fib 1 = 1
      fib n = memoizedFib (n - 2) + memoizedFib (n - 1)
   in (Prelude.map fib [0 ..] !!)

main :: IO ()
main = do
  print (slowFib 10)
  print (memoizedFib 10)

#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
Binary search implemented with recursion.
"""


# %% Find element in list using binary search
# During the last class before recursion,
# we covered binary search iteratively
def bin_search_rec(
    lst: list[int], item: int, low: int, high: int, indent: str = ""
) -> int:
    """
    Finds index of string in list of strings, else -1.
    Searches only the index range low to high
    Note: Upper/Lower case characters matter
    """
    print(indent, "find() range", low, high)
    range_size = (high - low) + 1
    mid = (high + low) // 2
    if item == lst[mid]:
        print(indent, "Found number.")
        pos = mid
    elif range_size == 1:
        print(indent, "Number not found.")
        pos = -1
    else:
        if item < lst[mid]:
            print(indent, "Searching lower half.")
            pos = bin_search_rec(lst, item, low, mid, indent + "    ")
        else:
            print(indent, "Searching upper half.")
            pos = bin_search_rec(lst, item, mid + 1, high, indent + "    ")
    print(indent, "Returning pos = %d." % pos)
    return pos


nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
pos = bin_search_rec(nums, 9, 0, len(nums) - 1)
if pos >= 0:
    print("\nFound at position %d." % pos)
else:
    print("\nNot found.")

#!/usr/bin/runghc

module AlgBinarySearch where

import Data.Vector as V

binarySearchWhere :: (Ord a) => V.Vector a -> a -> Int -> Int -> Maybe Int
binarySearchWhere coll element lo hi
  | hi < lo = Nothing
  | pivot < element = binarySearchWhere coll element (mid + 1) hi
  | element < pivot = binarySearchWhere coll element lo (mid - 1)
  | otherwise = Just mid
  where
    mid = lo + div (hi - lo) 2
    pivot = coll V.! mid

binarySearchLet :: (Ord a) => V.Vector a -> a -> Int -> Int -> Maybe Int
binarySearchLet coll element lo hi =
  let mid = lo + div (hi - lo) 2
      pivot = coll V.! mid
   in if hi < lo
        then Nothing
        else case compare pivot element of
          LT -> binarySearchLet coll element (mid + 1) hi
          GT -> binarySearchLet coll element lo (mid - 1)
          EQ -> Just mid

main :: IO ()
main = do
  print (binarySearchWhere (V.fromList [1 .. 30]) 30 0 29)
  print (binarySearchWhere (V.fromList ['a' .. 'z']) 'g' 0 29)
  print (binarySearchWhere (V.fromList [1, 3 .. 30]) 4 0 29)
  putStrLn ""
  print (binarySearchLet (V.fromList [1 .. 30]) 30 0 29)
  print (binarySearchLet (V.fromList ['a' .. 'z']) 'g' 0 29)
  print (binarySearchLet (V.fromList [1, 3 .. 30]) 4 0 29)

#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
Sudoku solver.
"""

# UNASSIGNED is used for empty cells in grid (a constant)
UNASSIGNED = 0


def solve_sudoku(grid: list[list[int]], indent: str = "") -> bool:
    """
    Takes a partially filled-in grid and attempts to assign values to all
    unassigned locations in such a way as to meet the requirements for Sudoku:
    non-duplication across rows, columns, and zones
    """
    row_col: list[int] = []
    # If there is no unassigned location, we are done
    # Otherwise, row and col are modified
    # (since they are passed by ref)
    if not find_unassigned_location(grid, row_col):
        # Total sucess
        return True
    row, col = row_col
    # consider digits 1 to 9
    for num in range(1, 10):
        # Does this digit produce any immediate conflicts?
        if is_safe(grid, row, col, num):
            # make tentative assignment
            grid[row][col] = num
            print(indent, "grid[", row, "]", "[", col, "] = ", num, sep="")
            # return, if success, yay!
            if solve_sudoku(grid, indent + " "):
                # like it occurs after recursive call
                return True
            else:
                # failure, un-do (backtrack) and try again
                grid[row][col] = UNASSIGNED
    print(indent, "grid[", row, "]", "[", col, "] = 1-9 all conflict!", sep="")
    # this triggers backtracking
    return False


def find_unassigned_location(grid: list[list[int]], row_col: list[int]) -> bool:
    """
    Searches the grid to find an entry that is still unassigned. If found, the
    reference parameters row, col will be end up set (by the for loop) to the
    location that is unassigned, and true is returned. If no unassigned entries
    remain, false is returned.
    """
    for row in range(len(grid)):
        for col in range(len(grid[0])):
            if grid[row][col] == UNASSIGNED:
                row_col[:] = row, col
                return True
    return False


def used_in_row(grid: list[list[int]], row: int, num: int) -> bool:
    """
    Returns a boolean which indicates whether any assigned entry in the
    specified row matches the given number.
    """
    for col in range(len(grid[0])):
        if grid[row][col] == num:
            return True
    return False


def used_in_col(grid: list[list[int]], col: int, num: int) -> bool:
    """
    Returns a boolean which indicates whether any assigned entry in the
    specified column matches the given number.
    """
    for row in range(len(grid)):
        if grid[row][col] == num:
            return True
    return False


def used_in_box(
    grid: list[list[int]], box_start_row: int, box_start_col: int, num: int
) -> bool:
    """
    Returns a boolean which indicates whether any assigned entry within the
    specified 3x3 box matches the given number.
    """
    for row in range(3):
        for col in range(3):
            if grid[row + box_start_row][col + box_start_col] == num:
                return True
    return False


def is_safe(grid: list[list[int]], row: int, col: int, num: int) -> bool:
    """
    Returns a boolean which indicates whether it will be legal to assign num to
    the given row,col location. Check if 'num' is not already placed in
    current row, current column and current 3x3 box
    """
    return (
        not used_in_row(grid, row, num)
        and not used_in_col(grid, col, num)
        and not used_in_box(grid, row - row % 3, col - col % 3, num)
    )


def print_grid(grid: list[list[int]]) -> None:
    """
    Prints the grid.
    """
    for row in grid:
        for element in row:
            print(element, " ", end="")
        print()


def main() -> None:
    # 0 for unassigned cells, as the constant at top
    grid = [
        [3, 0, 6, 5, 0, 8, 4, 0, 0],
        [5, 2, 0, 0, 0, 0, 0, 0, 0],
        [0, 8, 7, 0, 0, 0, 0, 3, 1],
        [0, 0, 3, 0, 1, 0, 0, 8, 0],
        [9, 0, 0, 8, 6, 3, 0, 0, 5],
        [0, 5, 0, 0, 9, 0, 6, 0, 0],
        [1, 3, 0, 0, 0, 0, 2, 5, 0],
        [0, 0, 0, 0, 0, 0, 0, 7, 4],
        [0, 0, 5, 2, 0, 6, 3, 0, 0],
    ]
    print("Problem is:")
    print_grid(grid)
    print("Solution is:")
    if solve_sudoku(grid):
        print_grid(grid)
    else:
        print("No solution exists")


if __name__ == "__main__":
    main()