How to prevent a recursion error implementing factorial in Python

Question

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

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
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
Of course the iterative one doesn't throw a recursion error. It isn't using recursion. — khelwood, Apr 21 '21 at 21:24
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
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
@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

score 0 · Answer 1 · answered Apr 21 '21 at 21:44

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

answered Apr 21 '21 at 21:44

griffin_cosgrove

419
8
16

Yes, I've checked it out however increasing the limit causes a segmentation fault. – CobraPi Apr 21 '21 at 21:50

score 0 · Answer 2 · answered Apr 21 '21 at 22:00

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)

How to prevent a recursion error implementing factorial in Python

2 Answers2