Recursive algorithm that multiplies specific natural numbers

Question

Design a recursive algorithm f(n1, n2, delta) that multiplies specific natural numbers between n1 and n2 (n1 > n2) as follows. Starting with n1 multiply all natural numbers with a distance of delta from the previous natural number.

Example: n1 = 35, n2 = 15, delta = 5 f(35, 15, 5) = 35 * 30 * 25 * 20 * 15

Solution:

Input: n1, n2 ∈ ℕ, n1 > n2, ∃ x ∈ ℕ: n2 + (x * delta) = n2 Output: n1 * (n1 - delta ) * (n1 – 2 * delta) * … * n2

f(n2, n2, delta) = n2 f(n1, n2, delta) = n1 * f((n1-delta), n2, delta)

Can someone explain this solution?

Answer 1

This solution implies a recursive algorithm (pseudo-code below). The idea in the solution is that you can "diminish" the problem by decreasing n1 by delta, and the stopping condition is that n1 is smaller than n2.

Note that the explanation you mentioned is a bit inaccurate as it does assumes that after some steps n2 is gotten, while you may reach some value < n2 (for example, if you change the 15 in the call f(35,15,5) to 14).

The pseudo-code:

f(n1, n2, delta):
    if n1 < n2:
        return 1
    return n1 * f(n1 - delta, n2, delta)

Running example on your case (f(n1) instead of f(n1,n2,delta) is used for brevity as only n1 is changes):

f(35) = 35 * f(30) =
        35 * 30 * f(25) =
        35 * 30 * 25 * f(20) =
        35 * 30 * 25 * 20 * f(15) =
        35 * 30 * 25 * 20 * 15 * f(10) =
        35 * 30 * 25 * 20 * 15 * 1