Thinking About Recursion

Fine.

Now what is (27 * 96)? (2 * 6 * 10) + (7 * 9 * 10) + (2 * 9 * 10 * 10) + (7 * 6). etc. [In real life you'd do this in binary and the multiplies by 10 become shifts.]

This is not usually the fastest way to do scalar multiplication, but it illustrates that:

1. Ordinary scalar multiplication is polynomial multiplication.

2. Polynomial multiplication is convolution.

3. And since we can [sometimes] speed up convolution by moving it to the Fourier domain, we can multiply numbers by taking their FFTs first, doing an elementwise multiplication, and then taking an inverse FFT. This actually pays off on very large numbers.

Multiplication is fun stuff.

  import os
  import os.path
  
  def list_files_recursive(path):
      filenames = os.listdir(path)
      for filename in filenames:
          fullname = os.path.join(path, filename)
          if os.path.isdir(fullname):
              yield from list_files_recursive(fullname) # recursively explore folders
          else:
              yield fullname

  import os
  import os.path
  
  def list_files_stack(path):
      folders = [path] # create stack of unexplored folders
      while folders: # repeat until stack is empty
          path = folders.pop() # pick a folder from stack
          filenames = os.listdir(path)
          for filename in filenames:
              fullname = os.path.join(path, filename)
              if os.path.isdir(fullname):
                  folders.append(fullname) # push folder to stack
              else:
                  yield fullname

Practical: If we right all of are programs and tail-recursive (returning a recursive call or constant at the end of the prgram) programs they are easy to transform into simple while loops with no stack. The idea is instead of calling another function just restart the current one with the updated arguments.

EX:

    f(n,x)=f(n-1,x+1)
    f(0,x)=x

    while(n > 0){
      n--;
      x++
    }

Theorectical: Think about Brainfuck or Turing machines, these computing frameworks can compute any computable function using only what amounts to while loops and infinite memory.

Given then that we can produce arbitrary control flow using only while loops, we can reproduce how recursive calls are computed in computers with stack frames (provided by our stack).