Recursive function that returns the smallest divisor

Question

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?

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
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
@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

Slaven Tojić · Accepted Answer · 2018-04-09T07:16:53.483

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).

edited Apr 09 '18 at 07:16

answered Apr 09 '18 at 07:13

Slaven Tojić

2,945
2
14
33

1

Or even `return n % d == 0 ? d : SmallestDivisor(n, ++d);` – Dmitry Bychenko Apr 09 '18 at 07:15
@FunnyBuzer I'm glad I could help! – Slaven Tojić Apr 09 '18 at 07:58

fubo · Answer 2 · 2018-04-09T07:16:32.157

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

edited Apr 09 '18 at 07:16

answered Apr 09 '18 at 07:09

fubo

44,811
17
103
137

score 1 · Answer 3 · answered Apr 09 '18 at 08:02

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;
}

Recursive function that returns the smallest divisor

3 Answers3