How can i make this factorial function recursive?

user_5353800 0
Viewed 72

A function that calculates (n-1)! , but with steps.

def function1(n, step):
    result = 1
    for i in range(1, n, step):
        result *= i

    return result

I'm not allowed to add any more parameters and I need to make it recursive. I've tried this:

def function2(n, step):
    if n < 0:
        return 1

    return n * function2(n-step, step)

But for let's say:

function2(6,3)

it wouldn't work, the first function will give me 1 * 4 and the second one would give me 6 * 3 * 1

I don't know how to make it work with the step argument.

Edit: Some more samples:

First function
function1(13, 3) == 280
function1(11, 3) == 280
function1(6, 3) == 4
function1(11, 2) == 945
function1(8, 2) == 105
function1(4, 2) == 3
More sample: 
function1(12, 3) == 280
function1(5, 2) == 3
function1(5, 3) == 4

Second function (same values):
function2(13, 3) == 3640
function2(11, 3) == 880
function2(6, 3) == 0
function2(11, 2) == 10395
function2(8, 2) == 0
function2(4, 2) == 0

Edit2: Some more clarifications: The function computes (n-1)!, but with steps. The step argument would just "step over" or "skip" some numbers (e.g.: function1(12, 3) should compute 1*4*7*10, like with the step argument from range(), cause it's used in the first function)

Thank you!

recursion python
2 Answers

The obvious difference is that you are building range starting at 1 and counting up to n by step, and in the recursive example you are starting at n and counting down by step. This will result in different numbers being multiplied.

Because you are required not to use any additional function parameters, I would suggest an inner helper function, loop -

def fact (n, step):
  def loop (m):
    if m >= n:
      return 1
    else:
      return m * loop(m + step)
  return loop(1)

If you don't want to use a helper function like loop above, you are constrained to complex modulus arithmetic -

def fact (n, step):
  if n % step != 1:
    return fact(n + 1, step)
  elif n < step:
    return 1
  else:
    return (n - step) * fact(n - step, step)

No matter which way you shake it, the modulus operation for this problem is messy -

def fact (n, step):
  q = (n - 1) % step
  if q:
    return fact(n + step - q, step)
  elif n < step:
    return 1
  else:
    return (n - step) * fact(n - step, step)

Once academic constraints like "do not use additional parameters" go away, you can multiply the ascending series in a more familiar way -

def fact (n, step, m = 1):
  if m >= n:
    return 1
  else:
    return m * fact(n, step, m + step)

All variations of fact above produce identical output -

print(fact(13, 3) == 280) # True
print(fact(11, 3) == 280) # True
print(fact(6, 3) == 4) # True
print(fact(11, 2) == 945) # True
print(fact(8, 2) == 105) # True
print(fact(4, 2) == 3) # True
print(fact(5, 2) == 3) # True
print(fact(5, 3) == 4) # True
user_6331830

Because the steps is calculated beginnig with 1 You have to normalize n to be a multiple of step plus 1 before you begin And you can cheat the number of arguments by setting the steps negative on recursive calls.

def function2(n, step):
    if n <= 1:
        return 1
    if step > 0: 
        n = n - 2
        n = n - n % step + 1
        step = -step
    return n * function2(n + step, step)
user_45240270
Related