Недостаточно памяти с простым кальцием?

Question

Я получаю out of memory с очень простым вычислением.

Я пытаюсь вычислить многие топологии, которые бинарное дерево могло бы дать n выборок

Поэтому я просто пытаюсь perl -E 'sub fac{ my ($n) = @_; $n == 1 ? 1 : $n * fac($n -1)} sub top{ my ($n) = @_; $t = fac(2 * $n - 5) / (2 ** ($n - 3) * fac($n - 3) ) } say top(3)' Кроме того, другая версия той же математики:

#!/usr/bin/env perl

use warnings;
use strict;
#use features;

sub factorial{
        my ($n) = @_;
        $n == 1 ? 1 : $n * factorial($n -1)
}

sub topologies{
        my ($n) = @_;
        my $a = (2 * $n) - 5;
        my $a_f = factorial($a);
        my $b = $n -3;
        my $b_f = factorial($b);
        my $c = 2 ** $b;
        my $q = $c * $b_f;
        my $t = $a_f / $q;
        return $t;
}

print "Enter number of taxas: ";
my $input = <STDIN>;
my $ntop = topologies();

print $ntop, "\n";

И когда я пытаюсь даже для размера выборки 3.Я получил out of memory в компьютере с 4 ГБ оперативной памяти и 4 ГБ кэш-памяти.То же самое относится к 128 ГБ или ram-серверу.

Мне не нужен этот calc, я просто попробовал для развлечения.Но я не могу понять, почему я получаю это сообщение out of memory.

РЕДАКТИРОВАТЬ: я просто получаю его, когда образец равен или меньше, чем 3

Answer 1

С $n = 3 ваши toplogies(3) будут звонить factorial(1) и factorial(0). Последний неправильно реализован и пытается создать факториал, вызывая factorial(-1), который затем вызывает factorial(-2), который затем вызывает factorial(-3) ..., то есть бесконечную рекурсию, где каждый шаг выделяет больше памяти. Эта бесконечная рекурсия приведет к нехватке памяти. Подобные вещи случаются с $n<3.