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

.css-j9qmi7{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-flex-direction:row;-ms-flex-direction:row;flex-direction:row;font-weight:700;margin-bottom:1rem;margin-top:2.8rem;width:100%;-webkit-box-pack:start;-ms-flex-pack:start;-webkit-justify-content:start;justify-content:start;padding-left:5rem;}@media only screen and (max-width: 599px){.css-j9qmi7{padding-left:0;-webkit-box-pack:center;-ms-flex-pack:center;-webkit-justify-content:center;justify-content:center;}}.css-j9qmi7 svg{fill:#27292D;}.css-j9qmi7 .eagfbvw0{-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;color:#27292D;}