CODEWITHSUNDEEP
javarecursion
NoSuchUserException
NoSuchUserException

Reputation: 149

Stack overflow exception with recursion

I am trying to make a program which calculates double factorial (example - n=3, => (3!)! = 6! = 720) but i have some issues with recursion bottom and i have stack overflow exception.

public static long df(long n) {
    if (n == 1) {
        return 1;
    } else {
        return df(n * df(n - 1));
    }
}

public static void main(String[] args) {
    System.out.println(df(3));
}

Upvotes: 1

Views: 165

Answers (4)

cdlane
cdlane

Reputation: 41872

We can do:

public static long factorial(long n) {
    return (n <= 1) ? 1 : n * factorial(n - 1);
}

public static long twice_factorial(long n) {
    return factorial(factorial(n));
}

And, if needed, with some trickery turn this into a single method:

public static long twice_factorial(long n) {

    return new Object() {
        long factorial(long n) {
            return (n <= 1) ? 1 : n * factorial(n - 1);
        }

        long twice_factorial(long n) {
            return factorial(factorial(n));
        }
    }.twice_factorial(n);
}

But this is a useless function as it's only good for n < 4 -- once we reach (4!)!, we exceed the limit of Java's long type:

(4!)! = 24! = 620,448,401,733,239,439,360,000
Java 'long' +max  = 9,223,372,036,854,755,807

If you want this function to be useful, you might use a floating approximation equation instead. But calling approximate factorial again on an approximation probably doesn't make much sense. You'd want a floating approximation equation for the nested factorial value itself.

Or, we can switch to BigInteger:

import java.math.BigInteger;

public class Test {

    public static BigInteger factorial(BigInteger n) {
        return (n.compareTo(BigInteger.ONE) <= 0) ? n : n.multiply(factorial(n.subtract(BigInteger.ONE)));
    }

    public static BigInteger twice_factorial(BigInteger n) {
        return factorial(factorial(n));
    }

    public static void main(String[] args) {
        System.out.println(twice_factorial(new BigInteger(args[0])));
    }
}

USAGE

> java Test 4
620448401733239439360000
>

But this only gets to (7!)! before we get java.lang.StackOverflowError! If we want to go further, we need to dump the recursion and compute the factorial iteratively:

public static BigInteger factorial(BigInteger n) {
    BigInteger result = BigInteger.ONE;

    while (n.compareTo(BigInteger.ONE) > 0) {
        result = result.multiply(n);

        n = n.subtract(BigInteger.ONE);
    }

    return result;
}

USAGE

> java Test 8
34343594927610057460299569794488787548168370492599954077788679570543951730
56532019908409885347136320062629610912426681208933917127972031183174941649
96595241192401936325236835841309623900814542199431592985678608274776672087
95121782091782285081003034058936009374494731880192149398389083772042074284
01934242037338152135699611399400041646418675870467025785609383107424869450
...
00000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000
>

Upvotes: 0

Gromph
Gromph

Reputation: 163

Firstly, define your factorial function:

Via Jupyter:

#include <iostream>
std::cout << "some output" << std::endl;

long fac(long n) {
    if( n == 1)
        return 1;
    else
        return n * fac((n-1));
}

And after define your function:

long double_fac(long n)
{
    long step_one = fac(n);
    return fac(step_one);
}

Factorielle-Algorythme

Upvotes: -2

Reut Sharabani
Reut Sharabani

Reputation: 31339

I think you should use mutual recursion with the help of factorial.

The general g-factorial function can compose factorial g times:

public static long gf(long n, long g) {
    if (g == 1){
        return fact(n);
    }
    return fact(gf(n, g - 1));
}

The specific double factorial can be gf(n, 2):

public static long df(long n) {
    return gf(n, 2);
}

And the factorial helper function:

public static long fact(long n) {
    if (n == 1) {
        return 1;
    } else {
        return n * fact(n - 1);
    }
}

Now test:

public static void main(String[] args) {
    System.out.println(df(3));
}

Upvotes: 1

phflack
phflack

Reputation: 2727

You're encountering an infinite loop with df(n * df(n - 1));

n * df(n-1) will compute the factorial, and you're inadvertently feeding your answer back into the recursive method, causing it to go on forever

Change

return df(n * df(n - 1));

to

return n * df(n - 1);

and you should get the correct result for factorials

Once you have this working recursive factorial method, it becomes much easier to create a double factorial by just using df(df(3))

Upvotes: 3

Related Questions