All Episodes

March 14, 2021 128 mins

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;}
Mark as Played

Advertise With Us

Popular Podcasts

Stuff You Should Know
24/7 News: The Latest

24/7 News: The Latest

The latest news in 4 minutes updated every hour, every day.

The Joe Rogan Experience

The Joe Rogan Experience

The official podcast of comedian Joe Rogan.

Music, radio and podcasts, all free. Listen online or download the iHeart App.

Connect

© 2025 iHeartMedia, Inc.