Show Recursion Show

We dig into recursion and learn that Michael is the weirdo, Joe gives a subtle jab, and Allen doesn't play well with others while we dig into recursion.

This episode's show notes can be found at https://www.codingblocks.net/episode154, for those that might be reading this via their podcast player.

Sponsors

• Datadog –  Sign up today for a free 14 day trial and get a free Datadog t-shirt after creating your first dashboard.

News

• Thank you all for the reviews:
  • iTunes: ripco55, Jla115
  • Audible: _onetea, Marnu, Ian

Here I Go Again On My Own

What is Recursion?

• Recursion is a method of solving a problem by breaking the problem down into smaller instances of the same problem.
  • A simple "close enough" definition: Functions that call themselves
• Simple example: fib(n) { n <= 1 ? n : fib(n - 1) + fib(n - 2) }
• Recursion pros:
  • Elegant solutions that read well for certain types of problems, particularly with unbounded data.
  • Work great with dynamic data structures, like trees, graphs, linked lists.
• Recursion cons:
  • Tricky to write.
  • Generally perform worse than iterative solutions.
  • Runs the risk of stack overflow errors.
• Recursion is often used for sorting algorithms.

How Functions Roughly Work in Programming Languages

• Programming languages generally have the notion of a "call stack".
  • A stack is a data structure designed for LIFO. The call stack is a specialized stack that is common in most languages
• Any time you call a function, a "frame" is added to the stack.
  • The frame is a bucket of memory with (roughly) space allocated for the input arguments, local variables, and a return address.
    • Note: "value types" will have their values duplicated in the stack and reference types contain a pointer.
• When a method "returns", it's frame is popped off of the stack, deallocating the memory, and the instructions from the previous function resume where it left off.
• When the last frame is popped off of the call stack, the program is complete.
• The stack size is limited. In C#, the size is 1MB for 32-bit processes and 4MB for 64-bit processes.
  • You can change these values but it's not recommended!
• When the stack tries to exceed it's size limitations, BOOM! … stack overflow exception!
• How big is a frame? Roughly, add up your arguments (values + references), your local variables, and add an address.
• Ignoring some implementation details and compiler optimizations, a function that adds two 32b numbers together is going to be roughly 96b on the stack: 32 * 2 + return address.
• You may be tempted to "optimize" your code by condensing arguments and inlining code rather than breaking out functions… don't do this!
  • These are the very definition of micro optimizations. Your compiler/interpreter does a lot of the work already and this is probably not your bottleneck by a longshot. Use a profiler!
• Not all languages are stack based though: Stackless Python (kinda), Haskell (graph reduction), Assembly (jmp), Stackless C (essentially inlines your functions, has limitations)

The Four Memory Segments

source: Quora

How Recursive Functions Work

• The stack doesn't care about what the return address is.
• When a function calls any other function, a frame is added to the stack.
• To keep things simple, suppose for a Fibonacci sequence function, the frame requires 64b, 32b for the argument and 32b for the return address.
• Every Fibonacci call, aside from 0 or 1, adds 2 frames to the stack. So for the 100th number we will allocate .6kb (100² * 32). And remember, we only have 1mb for everything.
• You can actually solve Fibonacci iteratively, skipping the backtracking.
• Fibonacci is often given as an example of recursion for two reasons:
  • It's relatively easy to explain the algorithm, and
  • It shows the danger