нахождение наибольшего простого множителя с использованием рекурсии в c

Даже решение проблемы использования постинкремента, чтобы рекурсия продолжалась вечно, это не подходит для рекурсивного решения - см. здесь, чтобы узнать почему, но все сводится к тому, насколько быстро вы можете уменьшить пространство поиска.

В то время как ваше разделение huge_number сокращает его довольно быстро, подавляющее большинство рекурсивных вызовов выполняется путем простого увеличения n. Это означает, что вы собираетесь использовать много пространства стека.

Вам тоже будет лучше:

• используя итеративное решение, при котором вы не взорвете стек (если вы просто хотите решить проблему) ^(a); или
• найти более подходящую задачу для рекурсии, если вы просто пытаетесь изучить рекурсию.

^(a) Пример такого зверя, смоделированный на основе вашего рекурсивного решения:

#include <stdio.h>

long long prime_factor_i (int n, long long huge_number) {
    while (n < huge_number) {
        if (huge_number % n == 0) {
            huge_number /= n;
            continue;
        }
        n++;
    }
    return huge_number;
}

int main (void) {
    int n = 2;
    long long huge_number =  60085147514LL;
    long long largest_prime = 0;

    largest_prime = prime_factor_i (n, huge_number);
    printf ("%lld\n", largest_prime);

    return 0;
}

Как видно из результатов этого итеративного решения, наибольший коэффициент равен 10976461. Это означает, что последний пакет рекурсий в вашем рекурсивном решении потребует глубины стека в десять миллионов кадров стека, что для большинства сред не так легко.

Если вам действительно необходимо использовать рекурсивное решение, вы можете уменьшить пространство стека до квадратного корня из этого, используя тот факт, что у вас нет необходимости для полной проверки до числа, но только до его квадратного корня.

Кроме того, кроме 2, все остальные простые числа нечетные, поэтому вы можете дополнительно сократить пространство поиска вдвое, проверив только два плюс нечетные числа.

Рекурсивное решение, учитывающее эти две вещи, будет:

long long prime_factor_r (int n, long long huge_number) {
    // Debug code for level checking.

    // static int i = 0;
    // printf ("recursion level = %d\n", ++i);

    // Only check up to square root.

    if (n * n >= huge_number)
        return huge_number;

    // If it's a factor, reduce the number and try again.

    if (huge_number % n == 0)
        return prime_factor_r (n, huge_number / n);

    // Select next "candidate" prime to check against, 2 -> 3,
    //   2n+1 -> 2n+3 for all n >= 1.

    if (n == 2)
        return prime_factor_r (3, huge_number);

    return prime_factor_r (n + 2, huge_number);
}

Как видите, я также удалил (на мой взгляд неудобную) конструкцию:

if something then
    return something
else
    return something else

Я предпочитаю код с меньшим отступом, который исходит из:

if something then
    return something
return something else

Но это только личные предпочтения. В любом случае, это снизит ваш уровень рекурсии до 1662 (раскомментируйте отладочный код для проверки), а не до десяти миллионов, довольно значительное сокращение, но все же не идеально. Это нормально в моей среде.

Вы имели в виду n+1 вместо n++. n++ увеличивает n после его использования, поэтому рекурсивный вызов получает исходное значение n.

Вы переполняете стек, потому что n ++ увеличивает значение пост-инкрементно, выполняя рекурсивный вызов с теми же значениями, что и в текущем вызове.

причина сбоя - переполнение стека. Я добавляю счетчик в вашу программу и выполняю ее (в ubuntu 10.04 gcc 4.4.3), счетчик останавливается на «218287» перед дампом ядра. Лучшее решение - использовать цикл вместо рекурсии.