recursion trace task - new member

[kazoo]

i am unsure if this is the right place to post but what i am about to ask looks very simple compared to what you guys post.

i have been set the following task:


This is an algorithm trace task. No implementation is required.

Read the following algorithm for the recursive function called Curiosity that needs two integers as
inputs and returns an integer value.

In the algorithm, MOD is an operator. It works with two integers to give the remainder when the first
integer is divided by the second.

This means that (example)
17 MOD 7 is 3
72 MOD 15 is 12



FUNCTION Curiosity(X:Integer;Y:Integer):Integer;
IF Y = 0 THEN
Curiosity = X
ELSE
Output Y and (X MOD Y)
Curiosity = Curiosity(Y,X MOD Y)
ENDIF
END Curiosity

(a) Write down the output when the function is called with
(i) Output ‘The answer is ’, Curiosity(120,42)
(ii) Output ‘The answer is ’, Curiosity(221,153)


(b) The function is called with
Output ‘The answer is ’, Curiosity(30,24)
Write down in full each line that is executed, but replace each variable with its actual value
and indicate on the IF statement line whether the result of the test is true or false.

(c) Describe the purpose of the algorithm.

(d) Rewrite the recursive function as an iterative algorithm.

i would be grateful if you could answer any parts, just to let you know i have the answers 6 and 17 for the first parts, however i am confused if this is correct as it is a recursive function. pls help.

[Hack]

I'm not sure if this is a VB6 question or a VB.NET question but it got posted in the VB.NET CodeBank so I'll start here.

Moved to VB.NET

If it is a .NET question, where version are you using?

[sevenhalo]

I'll assume VB.Net as well...

This is that recursive function in VB.Net:

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        Dim x As Int32 = 30
        Dim y As Int32 = 24
 
        Debug.Write("The answer is: " & Curiosity(x, y))
    End Sub
 
    Private Function Curiosity(ByVal x As Int32, ByVal y As Int32) As Int32
        If y = 0 Then
            Curiosity = x
        Else
            Debug.Write(x & " " & (x Mod y) & System.Environment.NewLine)
            Curiosity = Curiosity(y, x Mod y)
        End If
    End Function

The intial layout is as follows:

'Recursion 1
    Private Function Curiosity(30, 24) As Int32
        If 24 = 0 Then
            Curiosity = 30
        Else
            Debug.Write(30 & " " & (30 Mod 24) & System.Environment.NewLine)
            Curiosity = Curiosity(24, 30 Mod 24)
        End If
    End Function

Since the previous if/then evaluates to false, curiousity is called again with the new value. A pointer is left at that call (think of it as a stack) and the function executes again with the new values:

'Recursion 2
    Private Function Curiosity(24, 6) As Int32
        If 6 = 0 Then
            Curiosity = 24
        Else
            Debug.Write(24 & " " & (24 Mod 6) & System.Environment.NewLine)
            Curiosity = Curiosity(6, 24 Mod 6)
        End If
    End Function

Once again, the if/then evaluates to false and another pointer is added to the top of the stack when curiosity is caled again:

'Recursion 3
    Private Function Curiosity(6, 0) As Int32
        If 0 = 0 Then
            Curiosity = 6       'Recursion turns around and finishes all the prior function calls back to the original 
        Else
            Debug.Write(0 & " " & (0 Mod 6) & System.Environment.NewLine)
            Curiosity = Curiosity(0, 6 Mod 0)
        End If
    End Function

This time the if/then evaluates to true. The function runs and finsihes in its entirety and no further calls are being made. The call made in Recursion 2 will have a value. It will be 6 since that is what recursion 3 evaluated to. This is the important part of recursion and where all of its strength lies. It will now finish recursion 2's function until it reaches a return, end function or an exit function with the value it received. The same thing will happen again, it will finish and recursion 1 will have a value of 6 (since recursion 2 never changed the value after it received it, it stayed the same). Recursion 1 will finish it's code and then it will be returned to the initial call that was made. Your output will be 6.

This answers your B question entirely, but I'm leaving it up to you to figure out C and D. After you read through this a couple of times and maybe draw it out yourself, it should make more sense.

[kazoo]

thank you this helps me a lot and makes sense.