Estou tendo, por vezes, o mesmo problema. Não é causado pela recursão em si, mas pelo Linux saindo da memória. O Linux permite que os programas aloquem o espaço de que precisam até que não haja mais memória. Por causa disso, sua máquina se torna incapaz de lidar com operações primitivas.
O Windows se comporta de outra maneira. Deixa algum espaço livre para as suas necessidades. Seu código receberia um erro "Sem memória" e o sistema funcionaria muito devagar por um tempo, mas não totalmente congelado.
A mesma idéia é usada por fork-bomb attack, que pega toda a memória no sistema tão rápido que mesmo killall é incapaz de rodar.
Se o seu programa consome muita memória sem controle, ele logo morrerá e o Linux rodará OK. A única maneira que me ajudou a torná-lo mais rápido atualmente é enviar Ctrl-C para o terminal onde seu código é iniciado ou está tentando executar killall .