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
The Joe Rogan Experience

The Joe Rogan Experience

The official podcast of comedian Joe Rogan.

24/7 News: The Latest

24/7 News: The Latest

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

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

Connect

© 2025 iHeartMedia, Inc.