3

I wrote a function that computes recursively the smallest divisor of an integer n>1:

using System;                   
public class Program
{
    public static void Main()
    {
        int n = Convert.ToInt32(Console.ReadLine());
        Console.WriteLine(SmallestDivisor(n));
    }

    public static int SmallestDivisor(int n)
    {
        return SmallestDivisor(n, 2);
    }

    public static int SmallestDivisor(int n, int d)
    {
        if (n%d == 0)
            return d;
        else  
            return SmallestDivisor(n, d+1);
    }
}

My goal is to build a recursive function that takes only the integer n as an argument. Is there any possible alternative to avoid calling another auxiliary function taking as arguments integer n and d?

FunnyBuzer
  • 313
  • 2
  • 14
  • 3
    Provide a default value. https://stackoverflow.com/questions/3316402/method-overloading-vs-optional-parameter-in-c-sharp-4-0, https://stackoverflow.com/questions/3914858/can-i-give-a-default-value-to-parameters-or-optional-parameters-in-c-sharp-funct – CodeCaster Apr 09 '18 at 07:07
  • 2
    If you are learning about the _how_ of recursion then this is ok. But it is a bad example of _why_ you would use recursion. A simple for-loop would do. – H H Apr 09 '18 at 07:12
  • why does the function have to be recursive? relatively large prime number will give you StackOverflow exception – ASh Apr 09 '18 at 07:40
  • 1
    @HenkHolterman I'm making practice on recursion – FunnyBuzer Apr 09 '18 at 07:55
  • @HenkHolterman, recursion is limited by `n` value: `n` is a divisor of `n`. but stack size limitation won't allow large n values with this recursive approach – ASh Apr 09 '18 at 08:08

3 Answers3

6

There is no need for 2 method's one is just enough:

static void Main(string[] args)
{
    int n = Convert.ToInt32(Console.ReadLine());
    Console.WriteLine(SmallestDivisor(n));
}

public static int SmallestDivisor(int n, int d=2)
{
    if (n % d == 0)
        return d;
    return SmallestDivisor(n, ++d);
}

The parameter d is optinal because it has a default value of 2 and you can call the method like SmallestDivisor(n). If you want another value of d passed to the method just call SmallestDivisor(n,d).

Slaven Tojić
  • 2,945
  • 2
  • 14
  • 33
2

replace

public static int SmallestDivisor(int n, int d)

with

public static int SmallestDivisor(int n, int d = 2)

To provide a default value for d and make this parameter optional. Now you can call SmallestDivisor(n) or SmallestDivisor(n,3)

Named and Optional Arguments

fubo
  • 44,811
  • 17
  • 103
  • 137
1

recursive method will throw StackOverflow exeption on relatively large prime number (e.g. 15331). non-recursive solution doesn't have such problem

public static int MinimalDivisor(int n)
{
    if ( n % 2 == 0)
        return 2;

    for(int d = 3; d < n/2; d=d+2)
        if (n % d == 0)
           return d;

    return n;
}
ASh
  • 34,632
  • 9
  • 60
  • 82