CodingBlocks

Show Recursion Show

Mar 15 '21

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.

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 of this approach.

What is Tail Recursion?

The recursive Fibonacci algorithm discussed so far relies on backtracking, i.e. getting to the end of our data before starting to wind back.
If we can re-write the program such that the last operation, the one in “tail position” is the ONLY recursive call, then we no longer need the frames, because they are essentially just pass a through.
A smart compiler can see that there are no operations left to perform after the next frame returns and collapse it.
The compiler will first remove the last frame before adding the new one.
This means we no longer have to allocate 100² extra frames on the stack and instead just 1 frame.
A common approach to rewriting these types of problems involves adding an “accumulator” that essentially holds the state of the operation and then passing that on to the next function.
The important thing here, is that the your ONE AND ONLY recursive call must be the LAST operation … all by itself.

Joe’s (Un)Official Recursion Tips

Start with the end.
Do it by hand.
Practice, practice, practice.

Joe Recursion Joe’s Motivational Script

#!/usr/bin/env python3
import sys 

def getname(arg):
    print(f"{arg}")

    if arg == 'Joe':
        getname('Recursion')
    else:
        getname('Joe')
    return

if __name__ == "__main__":
    sys.setrecursionlimit(500) 
    print(f"Who is awesome?")

    try:
        getname('Joe')
    except:
        print("You got this!")

Recap

Recursion is a powerful tool in programming.
It can roughly be defined as a function that calls itself.
It’s great for dynamic/unbounded data structures like graphs, trees, or linked lists.
Recursive functions can be memory intensive and since the call stack is limited, it is easy to overflow.
Tail call optimization is a technique and compiler trick that mitigates the call stack problem, but it requires language support and that your recursive call be the last operation in your function.
FAANG-ish interviews love recursive problems, and they love to push you on the memory.

Resources We Like

Recursion (computer science) (Wikipedia)
Dynamic Programming (LeetCode)
Grokking Dynamic Programming Patterns for Coding Interviews (educative.io)
Boxing and Unboxing in .NET (episode 2)
IDA EBP variable offset (Stack Exchange)
What is the difference between the stack and the heap? (Quora)
Data Structures – Arrays and Array-ish (episode 95)
Function Calls, Part 3 (Frame Pointer and Local Variables) (codeguru.com)
How to implement the Fibonacci sequence in Python (educative.io)
Tail Recursion for Fibonacci (GeeksforGeeks.org)
Recursion (GeeksforGeeks.org)
Structure and Interpretation of Computer Programs (MIT)
Tail Recursion Explained – Computerphile (YouTube)
!!Con 2019- Tail Call Optimization: The Musical!! by Anjana Vakil & Natalia Margolis (YouTube)

Tip of the Week

How to take good care of your feet (JeanCoutu.com)
Be sure to add labels to your Kubernetes objects so you can later use them as your selector. (kubernetes.io)
- Example: kubectl get pods --selector=app=nginx
Security Now!, Episode 808 (twit.tv, grc.com)
- AdGuard Home (adguard.com)
  - Match CNAME records against the blocklists (GitHub)

Episode source

ALTERNATE UNIVERSE DEV

CodingBlocks

Show Recursion Show

Sponsors

News