Functional-Style Programming

• Programming paradigm focusing on evaluating mathematical functions
• Based on combining functions that don't modify their arguments
• Functions don't use or change the program's state
• Allows directly expressing mathematical concepts
• Functions solely use return values to communicate their results
• In theory, functions are completely independent of each other
• Prominent functional languages include Elixir, Erlang, Haskell and SML

Concepts of functional programming

Pure functions

Recursion

Function definition depends on (a simpler version of) itself

First-class and higher-order functions

Functions are first-class citizens

Anonymous (lambda) functions

Closures

an abstraction binding a function to its scope
a closure is a record storing a function together with an environment

Currying

Partially applying arguments to a function

...

What is Recursion?

Recursion is the term for functions calling themselves

• A recursive function depends on a simpler version of itself
• Recursive implementations can be re-implemented with loops
• Loops tend to be more efficient but harder to code

Purpose of Recursion

• Divide and conquer - serves as top-down approach to problem solving
  Allows focusing on the next step - not the whole problem at once
• Facilitates implementing certain algorithms
  • Data structures such as linked lists and trees
  • High level algorithms using such data structures (eg. graph algorithms)
  • Certain mathematical concepts can be expressed with straightforward, easy to read code

Which Problems does Recursion Cause?

• Watch out for the limit on the depth of recursion (avoid stack overflows)
• Overlapping sub-problems may be solved multiple times
  (can be avoided by dynamic programming and memoization)
• Function calls introduce performance overhead compared to loops
• The storage of recursive stack frames generally consumes more memory than equivalent iterative solutions
• Bugs risk infinite recursion

Example - Factorial of a Non-Negative Integer

$\text{factorial(n) = }\{\begin{array}{ll}1& \text{if n }\in \text{ set([0, 1])}\\ \text{n * factorial(n - 1)}& \text{otherwise}\end{array}$

#include <cstdint>
#include <iostream>

uint64_t factorial(uint32_t n) {
  if (n <= 1) return 1;  // base case
  return n * factorial(n - 1);  // recursion
}

int main() {
  std::cout << "factorial(5): " << factorial(5) << std::endl;
  return 0;
}

Example: Calculate the n^th Fibonacci number

$\text{fib(n) = }\{\begin{array}{ll}\text{n}& \text{if n }\in \text{ set([0, 1])}\\ \text{fib(n - 1) + fib(n - 2)}& \text{otherwise}\end{array}$

#include <cstdint>
#include <cstdlib>
#include <iostream>

uint64_t fib(uint32_t n) {
  if (n <= 1) return n;  // base case
  return fib(n - 1) + fib(n - 2);  // recursion (overlapping subproblems)
}

int main(int argc, char** argv) {
  uint32_t n{6};  // default value
  if (argc == 2) { n = std::atoi(argv[1]); }
  std::cout << "fib(" << n << "): " << fib(n) << std::endl;
  return 0;
}

Example: Fibonacci Numbers With Cache

Ideally, we wouldn't modify the original function

#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <map>

uint64_t fib(uint32_t n) {
  static std::map<uint32_t, uint64_t> cache;
  if (not cache.contains(n)) {
    if (n <= 1) cache[n] = n;  // base case
    else cache[n] = fib(n - 1) + fib(n - 2);  // recursion
  }
  return cache[n];
}

int main(int argc, char** argv) {
  uint32_t n{6};  // default value
  if (argc == 2) { n = std::atoi(argv[1]); }
  std::cout << "fib(" << n << "): " << fib(n) << std::endl;
  return 0;
}

Visualize execution