Implementing partial recursive function in C#

Question

I am having trouble with somwhow implementing a partial recursive function (at least in my mind though).

for any given p and arbitrary maxsteps = 100, calculate L:

How do you know when to stop? Is the function *always* like this, with that exact number of levels? — Lasse V. Karlsen, May 27 '19 at 08:33
I guess I don't understand your question then, if the given example have a maxsteps of 100. What is the relation between that value and the nested levels of that expression? It seems you did 3 or 4 steps depending on how you interpret the recursivity of it, but how does that relate to 100? — Lasse V. Karlsen, May 27 '19 at 08:37
It dose not really depend to 100, that value should be configured every time the code runs. — SHM, May 27 '19 at 08:38
your P remains same throughout all 100 iterations.. I see this is case of loop not recursion. As I think recursion should have been dependant on value of P and P should be moving the program towards exit condition. — Amit, May 27 '19 at 08:38
My point was that I want to know what maxsteps value you would have for your particular expression, the one that goes 3-4 levels deep. — Lasse V. Karlsen, May 27 '19 at 08:39
that 3 or 4 times is just for the sake of showing the formula — SHM, May 27 '19 at 08:39
Let me clarify, for that expression, is maxsteps 3 or is it 4 or is it something completely different? If you say it is 100, then I really don't understand your question. I'm asking about specifics related to your example, not what the general function should do. I understand that if you specify 100 it should nest 100 levels deep, but what is the maxsteps value of your specific example? Is it 3, or is it 4? — Lasse V. Karlsen, May 27 '19 at 08:40
Using recursion you may hit arbitrary limits imposed by the OS (StackOverflowException). Without recursion the limits are only the precision of the numeric type (double) — Theodor Zoulias, May 27 '19 at 08:40
Basically, I'm wondering if maxsteps == 1 would return `1 / (p+1)` or `1 / (p + 1 / (p + 1))`. — Lasse V. Karlsen, May 27 '19 at 08:43
Hi, is there anything you're still unsure about with this question? — ProgrammingLlama, Jul 02 '19 at 10:44

Mureinik · Answer 1 · 2019-05-27T08:39:31.120

7

You could pass the maxsteps down to the recursive function and subtract 1 on each step until you reach 0, with is the end condition:

public double L(double p, int maxSteps)
{
    if (maxSteps == 0)
    {
        return 1 / (p + 1);
    }
    return 1 / (p + L(p, maxSteps - 1));
}

edited May 27 '19 at 08:39

answered May 27 '19 at 08:38

Mureinik

297,002
52
306
350

ProgrammingLlama · Answer 2 · 2019-05-27T08:51:30.230

4

I appreciate you want a recursive function, but I figured I'd provide a non-recursive alternative in case it turns out to be preferred:

private static double CalculateL(double p, int maxsteps)
{
    double val = 1 / (p + 1);
    for (int i = 1; i <= maxsteps; ++i)
    {
        val = 1 / (p + val);
    }
    return val;
}

I'm not 100% sure about maxsteps, based on the other answers. If the answer isn't right, then you probably want < maxsteps where I've got <= maxsteps.

Also, please read Is floating point math broken? if you're expecting very precise results.

edited May 27 '19 at 08:51

answered May 27 '19 at 08:43

ProgrammingLlama

36,677
7
67
86

3

I'd certainly go with this approach as I don't think this problem needs recursion at all (why to give hard time to stack) – Amit May 27 '19 at 08:45
You could also wrap expression into (local) function. – Sinatr May 27 '19 at 08:45
@Lasse Oops, yes. You're right. I've corrected it to match the others. – ProgrammingLlama May 27 '19 at 08:46
1

Well, for all we know, your result was the right one. – Lasse V. Karlsen May 27 '19 at 08:47
@LasseVågsætherKarlsen +/-1 may not be that important. The function is probably converging to a real number. The more steps you go, the less significant the last step is. – Theodor Zoulias May 27 '19 at 08:48
1

You may be right, but in that case I would say that the right approach would probably be to specify an epsilon limit instead, instructing the algorithm to stop when the change to the value is less than some predefined small limit, instead of specifying exactly how many steps to run it. But yes, if you provide a sufficiently high number, +/- 1 step won't matter (that much). – Lasse V. Karlsen May 27 '19 at 08:49
And I'm no math wiz, but I assume there's no way to pick a `p` so that it doesn't converge? ie. each additional steps move it further away from some value, instead of closer? – Lasse V. Karlsen May 27 '19 at 08:51
@Marco Replying to your now-deleted comment: The original equation states that the inner-most caclulation is `1/(p + 1)`. Testing with `p = 5` and `maxsteps = 0`, my method (and the recursive ones presented below) yields `0.166666666666667`, but yours yields `0`. Setting yours to `maxsteps = 1` yields `2`, which also seems incorrect. – ProgrammingLlama May 27 '19 at 09:01
@John yes I stated it after asking, it's cause of the floating point precision, with the value I tried it doesn't work correctly – Marco Salerno May 27 '19 at 09:02

Marco Salerno · Answer 3 · 2019-05-27T09:03:55.753

There I left you the code for the recursive approach:

class Program
{
    static void Main(string[] args)
    {
        double recursiveL = CalculateL(100, 100);
        double notRecursiveLWrong = NotRecursiveCalculateLWrong(100, 100);
        double notRecursiveLRight = NotRecursiveCalculateLRight(100, 100);
    }

    private static double CalculateL(double p, int maxSteps)
    {
        if (maxSteps == 0)
        {
            return (1 / (p + 1));
        }
        else
        {
            return (1 / (p + CalculateL(p, maxSteps - 1)));
        }
    }

    private static double NotRecursiveCalculateLWrong(double p, int maxSteps)
    {
        double result = 0;
        for (int i = 0; i < maxSteps; i++)
        {
            result = (1 / (p + result));
        }
        return result;
    }


    private static double NotRecursiveCalculateLRight(double p, int maxSteps)
    {
        double result = 1 / (p + 1);
        for (int i = 0; i < maxSteps; i++)
        {
            result = (1 / (p + result));
        }
        return result;
    }
}

While making it I was thinking about the fact that for this problem, recursion isn't needed and now I can see that I'm not the only one.

I added my not recursive approach.

Edit:

If you try my code you will see that every method returns the same value, WATCHOUT, this is cause of the low precision in floating points.

The correct approach is NotRecursiveCalculateLRight which is stated in @John 's answer.

How is this different from [this answer](https://stackoverflow.com/a/56322472/10883465)? — Joelius, May 27 '19 at 08:42
I made it while he posted his answer. Anyway I added another solution. — Marco Salerno, May 27 '19 at 08:54
@MarcoSalerno Well you added another solution which is also provided already. This post contains two answers which are both already proposed. This answer does not add anything and should be removed. — Joelius, May 27 '19 at 09:02

Implementing partial recursive function in C#

3 Answers3