寿司 虚空編 002 メモ化再帰

sushi.py

import sys, threading, thread

memo = {}

def f(x):
  return x + 1

def b(m, n):
  if (m, n) not in memo:
    memo[(m, n)] = (
      f(n)        if m == 0 and n > 0 else
      b(m - 1, 1) if m > 0 and n == 0 else
      b(m - 1, b(m, n - 1))
    )
  return memo[(m,n)]

def g(x):
  return b(x, x)

def main():
  print g(3)   # 61
  print b(4,1) # 65533
  print b(4,2) # zsh: segmentation fault (core dumped)  python sushi.py

if __name__ == "__main__":
  sys.setrecursionlimit(1024*1024)
  thread.stack_size(128*1024*1024)
  threading.Thread(target=main).start()