How can I make one recursive function which does division using only addition and only 2 variables

user_14512284 0
Viewed 588

I have been recently given school work to make a recursive function that does division using only addition (no subtraction allowed) and has only 2 variables.

EDIT: A couple of notes based on the comments:

  • n1 is divided by n2. (n1:n2)

  • The answer should be a whole number (int) of how many times you can fit n2 inside n1 (8:3 should get 2, 8:4 should also get 2).

  • You can assume that the inputs are only whole positive numbers.

As asked in the comments, I will try my best to translate the assignment to English and make it as accurate as possible:

Write a recursive function named "PDiv" that gets two whole positive numbers and returns their whole quotient, using addition operations only.

I have tried to make it with 2 recursive functions like shown: (Assignment requires only one function, so it's not a right answer)

public static int PDiv(int n1, int n2)
{
    if (n1 < n2)
        return 0;
    else if (n1 == n2)
        return 1;
    else
        return PDiv(n1, n2 + n2, n2) + 1;
}

public static int PDiv(int n1, int n2, int con)
{
    if (n1 < n2)
        return 0;
    else if (n1 == n2)
        return 1;
    else
        return PDiv(n1, n2 + n2, con) + 1;
}

In addition to that, I have also tried that one which does work, but it's pretending to be wise while not really doing it with addition, but with the addition of a minus (basically subtraction). Example:

public static int PDiv(int n1, int n2)
{
    if (n1 < n2)
        return 0;
    else if (n1 == n2)
        return 1;
    else
        return PDiv(n1 + -n2, n2) + 1;
}

If anyone has an idea of how I can make it work, I would love to hear that! Thanks in advance!

addition recursion division algorithm c#
5 Answers

Here's one way we can achieve this, provided we can use the modulo operator and a local variable.

The idea is that if we know PDiv(n, m + m), we just need to know if we can still add one more m or not.

C# code:

using System;

public class Test
{
    public static int PDiv(int n, int m)
    {
        if (n < m)
            return 0;
        if (n == m)
            return 1;
  
        int k = PDiv(n, m + m);

        return k + k + (n % (m + m) < m ? 0 : 1);
    }

    public static void Main()
    {
        Console.WriteLine(PDiv(21, 3));
    }
}
user_20347870

And here's how we can do it with purely addition, comparison and assignment operations and two parameters, as requested, provided we are allowed a tuple return value. C# code:

using System;

public class Test
{
    // Returns (floor(n / m) * m, floor(n / m))
    public static (int, int) f(int n, int m){
        if (n < m)
            return (0, 0);
        if (n == m)
            return (n, 1);
  
        (int _n, int k) = f(n, m + m);

        if (_n + m > n)
            return (_n, k + k);
    
        return (_n + m, k + k + 1);
    }

    public static void Main()
    {
        for (int n=1; n<200; n++){
            for (int m=1; m<n; m++){
                (int _n, int nm) = f(n, m);
                if (nm != n / m)
                    Console.WriteLine($"Mismatch: { n }, { m }") ;
            }
        }

        Console.WriteLine("Test done.");
    }
}
user_20347870

Your only problem is, that you still compare n1 to n2 in your second method, when you use n2 = n2 + con, while con remains your staring n2 it should work.

    private int div(int n1, int n2)
    {
        if (n1 == n2) return 1;
        if (n1 < n2) return 0;
        return div(n1, n2, n2+n2) + 1;  
    }
    private int div(int n1, int n2, int runner)
    {
        if (n1 == runner) return 1;
        if (n1 < runner) return 0;
        return div(n1, n2, runner+n2) + 1;
    }
user_137057440 
d = a/b 
d * b + r = a

The second line gives the idea how to solve this in a recursive manner. Disregarding the remainder (r), sum up b until d*b > a. With that, all left to do is to keep track of how many times we had to add b together until it got greater than a.

int div_loop(int dividend, int divisor, int x, int n) {
  if (x > dividend)
     return (n-1);
  return div_loop(dividend, divisor, (x + divisor), (n+1));
}
int div(int dividend, int divisor) {
  return div_loop(dividend, divisor, 0, 0);
}

This should be in line with the requirements, as the requirements do not prohibit writing a helper function. And the main function only has 2 arguments, and it is a recursive solution, using only addition.

If C# had nested function (not sure if it has now, but it did not when I last programmed in C#), the div_loop() could be nested inside the div() function and the internal function could be considered an implementation detail (and have 2 less arguments). For example, in F#, this could look like this:

let div dividend divisor =
  let rec operate x n =
    if x > dividend
    then (n - 1)
    else operate (x + divisor) (n + 1)
  operate 0 0

From the Microsoft c# documentation, it appears C# now supports nested functions, going by the name of "local functions".

Hence, you can fulfill all your requirements as such:

int pdiv(int dividend, int divisor) {
  return div_loop(0, 0);
  int div_loop(int x, int n) {
    if (x > dividend) return (n-1);
    return div_loop(x+divisor, n + 1);
  }
}
user_22251040

you could also write it as one method:

public int recursive_div(int a, int b)
    {
        if (a < b)
        {
            return 0;
        }
        else if (b == 0)
        {
            return -1;
        }
        else if (a == b)
        {
            return 1;
        }
        else
        {
            return  recursive_div(a-b,b) +1 ;
        }
    }

the return -1 is just a catch value for dived by 0 error.

user_171776980
Related