For anyone wondering why installing linux-image-generic works, it's the dependency on the "linux-image-extra" for your kernel version. The zram driver is included in that dependency:

$ dpkg -L linux-image-extra-4.4.0-112-generic | grep zram
/lib/modules/4.4.0-112-generic/kernel/drivers/block/zram
/lib/modules/4.4.0-112-generic/kernel/drivers/block/zram/zram.ko

Without the package, the necessary driver might not be installed.