Recursion

[ozos]

Hi guys,

I have a bit of a formula which I am trying to put into a vb.net function and was hoping for some help in doing so. The question I have is:

Let f be the recursive function below, with f(1) = f(0) = 0. What is the value of f(1337)?
f(n) = f(n - 1) - 1 if n is divisible by 2 or 3
f(n) = f(n - 2) + 2 otherwise

Would something along the lines of this be correct?

Function F(N)
       
        If N Mod 2 = 0 Or N Mod 3 = 0 Then

            Return F(N - 1) - 1

        Else

            Return F(N - 2) + 2

        End If


    End Function

When I run the code I get a StackOverflowException error.

Secondly, I am wondering if there is some way of solving this formula without the use of a computer program?

Many thanks in advance!

Ozos

[dday9]

The StackOverflowException occurs because it is an infinite recursion. Take a pen and paper and try to solve for F(1), you'll find that this happens:

F(1) = F(1 - 2) + 2 which simplifies to F(-1) + 2
F(-1) = F(-1 - 2) + 2 which simplifies to F(-3) + 2
F(-3) = F(-3 - 1) - 1 which simplifies to F(-4) - 1
F(-4) = F(-4 - 1) - 1 which simplifies to F(-5) - 1 
F(-5) = F(-5 - 2) + 2 which simplifies to F(-7) + 2
'To infinity and beyond

[techgnome]

You're lacking an exit condition ... which it gives to you in the question - f(0) = 0

So if N = 0 it needs to return 0 ...that will then start the process of unwinding the recursion and a value ultimately returned.

-tg

[Shaggy Hiker]

However, if you make the initial argument large enough, you'll STILL get an exception overflow, which is an issue with recursive functions: They can be cool, but there is always a number of nested recursions above which you can't go, and that limit will be system specific. For this reason, I tend to avoid recursive functions where I can. They usually aren't all that efficient anyways, which is why you asked the second question: A formula that will give you the answer for all N is going to be superior to a recursive function in every case.

Figuring out that function might be kind of hard. A function that includes a condition is likely to be a bit hard to figure out.

[ozos]

Ah ok, I understand. I'll put the exit condition in and see whats what. Bit of a long shot I know but would you guys know of any way that could be done with paper and pen by way too?

Cheers!

[boops boops]

I think DDay pointed the way to work it out with pen and paper -- or on screen, in his case. Once your exit condition test is in place, work out the result of the function by hand with starting values of n = 2, 3, 4, 5 and so on. You'll soon notice a pattern in the results!

I'm assuming you can't start with n negative, by the way.

BB

[georgesutfin]

Hello
Is this a homework assign?
I agree with BB you need to start with n=2. f(0)=0 and f(1)=0 by your conditions.
I do not agree with dday9 as to the values.
I believe f(2)=-1, f(3)=-2, f(4)=-3, f(5)=0 and so on.
I wrote code that did not use resursion and believe f(1337)=444
In my experience dday9 is usually right. So... ?
George

[boops boops]

EDIT: George was right after all, and I was wrong. Reminder to self: never post opinions about code without testing them first! What I mistakenly wrote was this:

George, f(2) evaluates to f(2 - 1) - 1 = f(1) - 1. Since evaluation takes place from left to right, f(1) has to be calculated before the 1 can get subtracted; and it never does get subtracted, because evaluating the function f(1) returns 0 and that's the end of it. This kind of thing happens all the time.

BB

[georgesutfin]

BB I still don't think that is right.
f(2)= f(2-1)-1
f(2)=f(1)-1
f(2) = 0-1
f(2) = -1

George

[boops boops]

[EDIT]Embarrasingly, I dug myself even deeper into the muck by persevering in my erratic ways. As a warning to others, I leave the totally incorrect message below hanging around my neck while I take my punishment in the stocks. BB


George, what you are doing is not the same as a recursive function.

If any function, recursive or not, returns an expression like f() - 100000000, the computer will have to evaluate the function f() before subtracting 100000000. But if f returns a specific value (like 0) from a recursive function, that's the result. The function's work is finished. No subtractions. No appeals. The 100000000 is a forgotten pipe-dream. The result is 0.

The Return statement is in some respects similar to Exit Sub or Exit Function. Whatever comes after that is irrelevant; it's not part of the program flow. A recursive function needs a mechanism of this kind because otherwise it would go on forever or at least until you end up with StackOverflow (and you know what they're like).

BB

[ozos]

Hmm, I've put the exit condition in but still get the original exception.

    Function F(N)
       
        If N = 0 Then

            Return 0

        ElseIf N Mod 2 = 0 Or N Mod 3 = 0 Then

            Return F(N - 1) - 1

        Else

            Return F(N - 2) + 2

        End If


    End Function

Sorry if I am being stupid here. Thanks for the theoretical way of working out the end result on paper dday9. Am I right in assuming there is a way of doing this non-recursively, for example doing this in an exam? I would not have enough time to work this out line by line!

[Inferrd]

Hmm, I've put the exit condition in but still get the original exception.

There are 2 exit conditions:

Let f be the recursive function below, with f(1) = f(0) = 0. What is the value of f(1337)?

i.e. return 0 when N=1 and also when N=0.

[ozos]

There are 2 exit conditions: i.e. return 0 when N=1 and also when N=0.

Yes, I was being a dumb-ass. Thank you very much!

[boops boops]

This particular function can't be done non-recursively. Its whole purpose is probably to test your basic understanding of recursion. It will become clear once you use the function to calculate a series of values "on paper". Bear in mind that a Return statement with a literal value like Return 0 implies "here is the end result, now exit the calculation".

BB

[passel]

George, what you are doing is not the same as a recursive function.

If any function, recursive or not, returns an expression like f() - 100000000, the computer will have to evaluate the function f() before subtracting 100000000. But if f returns a specific value (like 0) from a recursive function, that's the result. The function's work is finished. No subtractions. No appeals. The 100000000 is a forgotten pipe-dream. The result is 0.

The Return statement is in some respects similar to Exit Sub or Exit Function. Whatever comes after that is irrelevant; it's not part of the program flow. A recursive function needs a mechanism of this kind because otherwise it would go on forever or at least until you end up with StackOverflow (and you know what they're like).

BB

This particular function can't be done non-recursively. Its whole purpose is probably to test your basic understanding of recursion. It will become clear once you use the function to calculate a series of values "on paper". Bear in mind that a Return statement with a literal value like Return 0 implies "here is the end result, now exit the calculation".

BB

I'm not sure what you're trying to say here boops.
Any statements after a Return statement won't be executed, but the subtraction of 1 or the adding of 2 is not another statement, it is part of the statement that contains the function call.
The function will return, and the subtraction or addition will be done and returned.

Whether you code the function recursively or code it using loops and conditionals (non-recursively), the answer will be the same, i.e. 444 for the input value of 1337.

If the subtraction wasn't done, then changing the - 1 to - 3 or - 5 would make no difference, but of course it does make a difference.
I'm really not sure what your point is.

p.s. Here are my recursive and non-recursive versions of the function

  Function F(N As Integer) As Integer  'Recursive
    If (N = 0) Or (N = 1) Then
      Return 0

    ElseIf (N Mod 2 = 0) Or (N Mod 3 = 0) Then
      Return F(N - 1) - 1

    Else
      Return F(N - 2) + 2
    End If
  End Function

  Function F2(N As Integer) As Integer  'NonRecursive
    Dim r As Integer
    Do
      If (N = 0) Or (N = 1) Then
        Exit Do
      ElseIf (N Mod 2 = 0) Or (N Mod 3 = 0) Then
        N -= 1
        r -= 1
      Else
        N -= 2
        r += 2
      End If
    Loop
    Return r
  End Function

Also, as noted, you should see a repetitious pattern, which can be calculated for an input N (0 to ....) without using a loop.

  Function F3(N As Integer) As Integer
    Dim r, i As Integer

    If N = 0 Then Return 0

    i = (N - 1)
    r = (i \ 6) * 2
    i = i Mod 6
    If i <> 0 Then
      r -= i Mod 4
    End If
    Return r
  End Function

Test:

  Private Sub Button2_Click(sender As System.Object, e As System.EventArgs) Handles Button2.Click
    For i As Integer = 0 To 1337
      Debug.Print("In: {0,4} Out:(F: {1,3}, F2: {2,3}, F3: {3,3} )", i, F(i).ToString, F2(i).ToString, F3(i).ToString)
    Next
  End Sub

Example Output:

                                          'Note the pattern, incrementing by 2 in a cycle of 6
In:    0 Out:(F:   0, F2:   0, F3:   0 )
In:    1 Out:(F:   0, F2:   0, F3:   0 )  '<===   0
In:    2 Out:(F:  -1, F2:  -1, F3:  -1 )
In:    3 Out:(F:  -2, F2:  -2, F3:  -2 )
In:    4 Out:(F:  -3, F2:  -3, F3:  -3 )
In:    5 Out:(F:   0, F2:   0, F3:   0 )
In:    6 Out:(F:  -1, F2:  -1, F3:  -1 )
In:    7 Out:(F:   2, F2:   2, F3:   2 )  '<===   2
In:    8 Out:(F:   1, F2:   1, F3:   1 )
In:    9 Out:(F:   0, F2:   0, F3:   0 )
In:   10 Out:(F:  -1, F2:  -1, F3:  -1 )
In:   11 Out:(F:   2, F2:   2, F3:   2 )
In:   12 Out:(F:   1, F2:   1, F3:   1 )
In:   13 Out:(F:   4, F2:   4, F3:   4 )  '<===   4
In:   14 Out:(F:   3, F2:   3, F3:   3 )
In:   15 Out:(F:   2, F2:   2, F3:   2 )
In:   16 Out:(F:   1, F2:   1, F3:   1 )
In:   17 Out:(F:   4, F2:   4, F3:   4 )
In:   18 Out:(F:   3, F2:   3, F3:   3 )
In:   19 Out:(F:   6, F2:   6, F3:   6 )  '<===   6

'.....

In: 1316 Out:(F: 437, F2: 437, F3: 437 )
In: 1317 Out:(F: 436, F2: 436, F3: 436 )
In: 1318 Out:(F: 435, F2: 435, F3: 435 )
In: 1319 Out:(F: 438, F2: 438, F3: 438 )
In: 1320 Out:(F: 437, F2: 437, F3: 437 )
In: 1321 Out:(F: 440, F2: 440, F3: 440 )  '<===   440
In: 1322 Out:(F: 439, F2: 439, F3: 439 )
In: 1323 Out:(F: 438, F2: 438, F3: 438 )
In: 1324 Out:(F: 437, F2: 437, F3: 437 )
In: 1325 Out:(F: 440, F2: 440, F3: 440 )
In: 1326 Out:(F: 439, F2: 439, F3: 439 )
In: 1327 Out:(F: 442, F2: 442, F3: 442 )  '<===   442
In: 1328 Out:(F: 441, F2: 441, F3: 441 )
In: 1329 Out:(F: 440, F2: 440, F3: 440 )
In: 1330 Out:(F: 439, F2: 439, F3: 439 )
In: 1331 Out:(F: 442, F2: 442, F3: 442 )
In: 1332 Out:(F: 441, F2: 441, F3: 441 )
In: 1333 Out:(F: 444, F2: 444, F3: 444 )  '<===   444
In: 1334 Out:(F: 443, F2: 443, F3: 443 )
In: 1335 Out:(F: 442, F2: 442, F3: 442 )
In: 1336 Out:(F: 441, F2: 441, F3: 441 )
In: 1337 Out:(F: 444, F2: 444, F3: 444 )

[passel]

...

    Function F(N)
        If (N = 0) Or (N = 1)Then
            Return 0
        ElseIf N Mod 2 = 0 Or N Mod 3 = 0 Then
            Return F(N - 1) - 1
        Else
            Return F(N - 2) + 2
        End If
    End Function

... Am I right in assuming there is a way of doing this non-recursively, for example doing this in an exam? I would not have enough time to work this out line by line!

The answer is yes, but you would have to do enough of them to figure out the pattern.
But since the function is recursive, the values can build on themselves so once you hit a number that you've already done, you can use its result and not have to continue the loop.
For example, the function you have above. I would start writing the inputs and determine the outputs starting with 0 or 1.

I put the description in a code window to get fixed space formatting and leading spaces if needed. You could copy it into notepad for easier reading.
I show the input ==> output, but then show how the output was determine. I didn't actually write the output on the line until after I did what is described for each line.

0  ==>  0    ' 0 in 0 out  'a given return value
1  ==>  0    ' 1 in 0 out  'a given return value
2  ==> -1    ' 2 Mod 2 is 0, Call F(N-1). We know f(1)  returns  0, so  0 - 1 = -1
3  ==> -2    ' 3 Mod 3 is 0, Call F(N-1). We know f(2)  returns -1, so -1 - 1 = -2
4  ==> -3    ' 4 Mod 2 is 0, Call F(N-1). We know f(3)  returns -2, so -2 - 1 = -3
5  ==>  0    ' 5 else case , Call F(N-2). We know f(3)  returns -2, so -2 + 2 =  0
6  ==> -1    ' 6 Mod 2 is 0, Call F(N-1). We know f(5)  returns  0, so  0 - 1 = -1

7  ==>  2    ' 7 else case , Call F(N-2). We know f(5)  returns  0, so  0 + 2 =  2
8  ==>  1    ' 8 Mod 2 is 0, Call F(N-1). We know f(7)  returns  2, so  2 - 1 =  1
9  ==>  0    ' 9 Mod 3 is 0, Call F(N-1). We know f(8)  returns  1, so  1 - 1 =  0
10 ==> -1    '10 Mod 2 is 0, Call F(N-1). We know f(9)  returns  0, so  0 - 1 = -1
11 ==>  2    '11 else case , Call F(N-2). We know f(9)  returns  0, so  0 + 2 =  2
12 ==>  1    '12 Mod 2 is 0, Call F(N-1). We know f(11) returns  2, so  2 - 1 =  1

13 ==>  4    '13 else case , Call F(N-2). We know f(11) returns  2, so  2 + 2 =  4

At this point you might notice some patterns, like the six sequence cycle of Mods and Else cases, M M M E M E  M M M E M E 
You might notice that each else case where you add 2, is going up by 2 from the previous matching else in the cycle of six
(i.e 5 ==> 0, and 11 ==> 2, which would mean 17 ==> would likely be 4 and 23 would likely be 6)
(likewise, 7 ==> 2 and 13 ==> 4, which would mean 19 would likely be 6 and 25 would likely be 8)

Another thing you might note is the values between those key values follow a relative pattern. (-1, -2, -3, 0, -1)
Example 7 ==> 2, so the next 5 (8 through 12) should follow the relative pattern.
 2 + ( -1, -2, -3, 0, -1) i.e. 8:1, 9:0, 10:-1, 11:2, 12:1

So, 13 ==> 4, so the next 5 (14 to 18) should be 4 + (-1, -2, -3, 0, -1).

Given you have a cycle of six, and a relative pattern to add to that, you should be able to calculate what 1337 should be.
First you have to determine where a good starting point for the cycle is.
I think the 1, 7, 13, 19... are good reference points (F(n) = 0, 2, 4, 6, ...)
We want x mod 6 to give 0 to 5, so x has to be (n - 1) 1, 7, 13... becomes 0, 6, 12 to the mod function and \ operation)
(1337-1) \ 6  = 222. Since we increment by 2 each cycle of 6 multiply by 2 (222 * 2 = 444)
(1337-1) mod 6 = 4  'look at the 4th value in the relative pattern( -1, -2, -3, 0, -1) and add it to 444.

'Trying a few more to see it matches the function output
(1331-1) \ 6 = 221 with remainder of 4: 221*2 = 442 + 4th relative value (442 +  0 = 442)
(1332-1) \ 6 = 221 with remainder of 5: 221*2 = 442 + 5th relative value (442 + -1 = 441)
(1333-1) \ 6 = 222 with remainder of 0: 222*2 = 444
(1334-1) \ 6 = 222 with remainder of 1: 222*2 = 444 + 1st relative value (444 + -1 = 443)
(1335-1) \ 6 = 222 with remainder of 2: 222*2 = 444 + 2nd relative value (444 + -2 = 442)

Lots of detail here, but actually quite doable on paper if you had to.

[passel]

Out of curiosity, I wanted to time each function to see the difference between recursive and non-recursive. The straight code function was also called, but of course since it is straight code (no loops) it will always take about the same amount of time regardless of the size of the number passed to the function.
I first passed a million, but the recursive overflowed the stack.
The non-recursive took around 5ms, but sometimes as much as 14ms, so I think Windows OS overhead got in the way occasionally.
The straight calculation always returned around 2 microseconds or less. This is true of 1,000,000 or 100,000 or 10,000 so no need to comment on that further.

I next tried 100 thousand, but the recursive still overflowed the stack.
The non-recursive function generally took 500 to 600 microseconds, but also occasionally took around 1400 microseconds so Windows still seems to get in the way (or perhaps it is the .Net Garbage Collector taking some time).

I next tried 10 thousand. The recursive function could now complete without overflowing the stack.
Each of the functions showed periodic large variances in time, and I feel in might indeed be GC overhead in the background occasionally is the cause.
But here is the result from 3 runs.
Function F(10000) took 278.68 microseconds
Function F2(10000) took 88.02 microseconds
Function F3(10000) took 1.18 microseconds

Function F(10000) took 278.68 microseconds
Function F2(10000) took 99.08 microseconds
Function F3(10000) took 0.79 microseconds

Function F(10000) took 318.15 microseconds
Function F2(10000) took 105.79 microseconds
Function F3(10000) took 1.18 microseconds

It looks like the "straight" calculation might be running up against the resolution of the timer the stopwatch uses for its timing. This machine reports the stopwatch frequency as 2,533,388 so that would make the resolution around 0.394728 microseconds, so the reported times would be some multiple of that value.

[boops boops]

I'm not sure what you're trying to say here boops.
Any statements after a Return statement won't be executed, but the subtraction of 1 or the adding of 2 is not another statement, it is part of the statement that contains the function call.
The function will return, and the subtraction or addition will be done and returned.

You are completely right and I was mistaken, of course, as I was able to check using your recursive function code. Thanks to you, and George, for correcting me. I have edited my previous messages in this thread to avoid confusing other people who come to this thread looking for information. BB