-3

I'm developing a math suite and am currently having issues implementing the recursive version of the factorial function. The issue is when I use it in my Bayesian combination function:

C(n,k) = n! / k! * (n-k)!

I've tested it independently and it works as it should, but as soon as I put it in my combination function, I get the error Recursion Error: maximum recursion depth exceeded in comparison, even for very small values of n and k.

I've implemented an iterative solution which works perfectly, so why do I keep getting a recursion error?

Here's the recursive implementation:

def factorial(n):
    if n == 1 or n == 0:
        return n
    else:
        return n * factorial(n - 1)

Here's the iterative implementation:

def factorial(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result

And they are used in the combination function like so:

def combination(n, k):
    result = factorial(n) / (factorial(k) * factorial(n - k))
    return result

The recursive function seems to work only when k = 1.

Here are some sample outputs which produces the recursion error:

combination(2,1) = 2

combination(2,2) = 

Traceback (most recent call last):
  File "baysian.py", line 44, in <module>
    answer = combination(n, k)
  File "baysian.py", line 18, in combination
    result = factorial(n) / (factorial(k) * factorial(n - k))
  File "baysian.py", line 9, in factorial
    return n * factorial(n - 1)
  File "baysian.py", line 9, in factorial
    return n * factorial(n - 1)
  File "baysian.py", line 9, in factorial
    return n * factorial(n - 1)
  [Previous line repeated 994 more times]
  File "baysian.py", line 6, in factorial
    if n == 1:
RecursionError: maximum recursion depth exceeded in comparison
CobraPi
  • 372
  • 2
  • 9
  • 1
    What is your question? If you want to know which algorithm is faster, then time them. Don't post speculative guessing here; you have the proper authority in front of you. Look up how to use `timeit`, do the experiment, and post here with those results if there's a specific question you have. – Prune Apr 21 '21 at 21:21
  • 1
    Your recursive function does not guard against unexpected arguments, and will recurse infinitely (until it crashes) if the argument it receives is zero, negative, or a fraction. – khelwood Apr 21 '21 at 21:22
  • I'm asking why my recursive factorial function gives me the error 'maximum recursion depth exceeded in comparison' while my iterative one doesn't. – CobraPi Apr 21 '21 at 21:23
  • 1
    Of course the iterative one doesn't throw a recursion error. It isn't using recursion. – khelwood Apr 21 '21 at 21:24
  • 1
    Can you provide an example where `combination` overflows, but the recursive `factorial` does not? As a side note, the factorial formula is not really suitable for computing binomial coefficients, see https://en.wikipedia.org/wiki/Binomial_coefficient#Computing_the_value_of_binomial_coefficients for other options. – georg Apr 21 '21 at 21:27
  • @georg I'm not sure what you mean by showing where `combination` overflows but I know that the recursive solution works only when `k = 1` – CobraPi Apr 21 '21 at 21:34
  • 2
    You said: `I get the error Recursion Error: maximum recursion depth exceeded in comparison, even for very small values of n and k.` - post some code that reproduces the problem. – georg Apr 21 '21 at 21:35
  • consider editing your post with the actual question and the specific part of the code you have questions about. – griffin_cosgrove Apr 21 '21 at 21:43
  • What happens when you call the recursive version of `factorial(0)`? – Woodford Apr 21 '21 at 21:44
  • @Woodford I got a recurssion error, but I've edited the code to handle that case. – CobraPi Apr 21 '21 at 21:50
  • 1
    @CobraPi Are you sure that 0! == 0? – Woodford Apr 21 '21 at 21:54
  • @Woodford ugh I completely overlooked that. I think that was what was causing this error. Everything seems to be working now. Thanks! – CobraPi Apr 21 '21 at 21:58

2 Answers2

0

From this page:

import sys
print(sys.getrecursionlimit())

Then adjust with:

sys.setrecursionlimit(<number>)

Will crash your machine if you enter a number too high

griffin_cosgrove
  • 419
  • 8
  • 16
0

It turns out that my recursive factorial implementation was incorrect. It would return 0 for !0 instead of 1. I've added some changes and now it works. Here's my revised solution.

def factorial(n):
    if n == 1:
        return n
    elif n == 0:
        return 1
    else:
        return n * factorial(n - 1)
CobraPi
  • 372
  • 2
  • 9