Recursive function

[nd0911]

Hello,

I need a function that gets a variable number (byte its Ok), and do the following:

if the variable is 1 it will do the resulte of this function:

For Each v In Array(1, 2, 3, 4)
   Debug.Print v
Next

if the the variable is 2 it will do the resulte of this function:

    For Each v In Array(1, 2, 3, 4)
        For Each vv In Array(1, 2, 3, 4)
            Debug.Print v, vv
        Next
    Next

if the the variable is 3 it will do the resulte of this function:

For Each v In Array(1, 2, 3, 4)
    For Each vv In Array(1, 2, 3, 4)
        For Each vvv In Array(1, 2, 3, 4)
            Debug.Print v, vv, vvv
        Next
    Next
Next

and so on........

of course it should be dynamic, dont use "select case" (for the variable) or somthing like that.

I think it needs to be a recursive function, but I'm not sure.

 

[joeu2004]

I think it needs to be a recursive function, but I'm not sure.

A function per se?! For debug.print?!

It does not have to be recursive. But I do not have time to design the (straight-forward) iterative solution.

The following does what you ask. You can call if from Excel; for example, =doit(3)

Function doit(ByVal n As Long, Optional ByVal s As String = "")
Dim x As Variant, v As Long
If n = 1 Then
    For v = 1 To 4
        Debug.Print Mid(s & vbTab & v, 2)
    Next
Else
    For v = 1 To 4
        x = doit(n - 1, s & vbTab & v)
    Next
End If
End Function

To bulletproof against invalid values of initial n, change Else to ElseIf n > 0 Then.

 

[Eric W]

Here's a non-recursive way to do it:

Sub VariableCounter()
Dim NumIx As Long, Indexes() As Long, Maxes() As Long, i As Long

    NumIx = 3                       ' How many levels do you want?
    ReDim Indexes(1 To NumIx)       ' set the array to hold the counters
    ReDim Maxes(1 To NumIx)         ' set the array to hold the max values for each level
    For i = 1 To NumIx              ' for each level:
        Maxes(i) = 4                ' set the max
        Indexes(i) = 1              ' set the starting value
    Next i
        
NextOne:
    For i = 1 To NumIx              ' This part just prints out each index, I assume
        Debug.Print Indexes(i),     ' you actually want to do something else with
    Next i                          ' the indices.
    Debug.Print
    
    For i = 1 To NumIx              ' This part increments the indices.  Think odometer.
        Indexes(i) = Indexes(i) + 1 ' Add 1 to the leftmost index.  If it is in the right
        If Indexes(i) <= Maxes(i) Then GoTo NextOne:    ' range, go and process it.
        Indexes(i) = 1              ' If it exceeds the range, set it back to the starting
    Next i                          ' point, and increment the next one.  If you get all
                                    ' the way through the loop, you've done them all.
End Sub

I invented this code years ago when I was working with permutations. I wish I could have patented it! But I know it's been independently created many times since then. Like joeu2004, I assume you really don't want a Function to do a Debug.Print, you just want the logic to create and increment indices of varying numbers. Starting with this basic structure, you can modify it a lot. Count up from right to left instead of left to right. The Max values can be different for each level. You can actually use an Array(1,3,4,9) if you want, using the Index(i) as an index to the Array.

Anyway, hope this helps.

 

[lrobbo314]

Eric, do you think there is any inherent advantage to not doing it recursively? I guess if he was dealing with really big arrays, or a lot of them, he could run out of stack space. Is there a performance cost to doing it recursively? Just curious.

 

[Eric W]

I'd say it really depends on the situation. Stack space is certainly one consideration. Another is that in joeu2004's implementation, he's passing a string variable with the results, meaning that if you want to use the numbers as indices, you'll have to add another step to break it up. But that can be changed easy enough.

There often is a performance cost in doing things recursively, since every time you call the function, the interpreter has to create another copy of all the variables, and that takes some time. I love a well-designed recursive program, it often is quite elegant and easy to understand. But you also have to watch out for a good design. For example, the function

Function Fibonacci(n As Long)
    If n < 3 Then
        Fibonacci = 1
    Else
        Fibonacci = Fibonacci(n - 1) + Fibonacci(n - 2)
    End If
End Function

is often used as an introductory example for recursive programs. But computationally, it's horrible! For larger values, it calls itself for the same value multiple times. It is an axiom in computer science than anything you can do in a recursive program, you can do in a non-recursive program. But I don't know if there's a general way to say which is better in a given situation.

 

[joeu2004]

I wish I could have patented it! But I know it's been independently created many times since then

And long before. "I" invented a similar algorithm 40+ years ago. And truth be told, I might have leveraged an implementation that was published in "Dr Dobbs Journal", or Knuth or .... (But I think I was doing it in machine language, even before DDJ.)

Digression.... I object to patenting software algorithms, with the exception of implementations that solve mathematical and other scientific problems, where it is really the mathematics or science that is the invention. Generally, software implementations are more like books than machines. The exact form ("expression of ideas") might be copyrighted, but the "ideas" are not unique. And even the form might not be distinguishable. The only difference between Eric's implementation and mine might be the choice of variable names, perhaps avoiding the GoTo (although I am not "religious" about that; I'm good with whichever way looks "cleaner"), and using a Const statement for Eric's NumIx. That said, I know that the US patent office disagrees with me (sigh).

Anyway, thanks for stepping up, Eric.

-----

As for the question about recursion v. iteration....

Often, it depends. For example, we sometimes see a recursive implementation to calculate the factorial. IMHO, those are "just for fun", because obviously an iterative implementation is more efficient, when you consider the call overhead. Yes, there are risks of stack overflow; but much less so in modern operating systems. And yes, there can be overhead for recursion, mostly in the allocation of local variables.

In fact, those are the factors that I would use as criteria in choosing between recursion and iteration; that, and again whichever way looks "cleaner". For example, if the iterative method required the creation of temp arrays for each iteration -- or it required backing out changes for each iteration -- I would probably opt for a recursive implementation, where such changes are built into the nature of recursive procedures.

 

[Eric W]

And long before. "I" invented a similar algorithm 40+ years ago.

When I said "years ago", I specifically avoided saying how many years that was to avoid outing my age. But I first came up with the basic idea in high school in 1977, about 43 years ago! So it seems we're of a generation.

I agree wholehearted with you about patenting computer code, I don't like the idea of it. I agree people should not decompile or copy other commercial programs, but I consider that more of a copyright issue. Basic algorithms should not be patentable. I don't know if you remember during the Y2K issue, there was some guy who tried to patent a "windowing" technique to decide if a 2-digit year was in the 1900's or the 2000's. Anyone who's programmed more than 15 minutes could come up with that idea, and many did before he did. He was trying to work the system to get an unearned windfall. Fortunately, he didn't get far.

I also agree with you about the use of GoTo. I almost replaced that version with one that doesn't have a GoTo in it. But it was slightly longer, slightly more awkward looking (IMO), and still required one statement that wasn't real clear what it was doing. I avoid GoTo whenever possible, but favor clean design over strict removal of them. In a language such as VBA, where GoTo is required in some cases, I'm not as strict.

 

[joeu2004]

So it seems we're of a generation.

Yes. And when I "40+ years ago", I should have written "50+". That's what I wrote initially; then I did the math -- incorrectly (1968+50 = 2028 [sic]. Klunk!)
I guess that's why God created computers.

 

[lrobbo314]

Thanks for the explanation Eric. I had an idea that recursive had some downfalls. Not to mention, even though they can be powerful, I hate them because they make my head hurt. I can write the factorial recursive, but much past that I need some Motrin, lol. And I fancy myself a decent programmer.

As a side note: I dig your algorithm, but I hate GOTO statements. It might be elitist BS on my part, but it seems like cheating to me. I know it's irrational and dumb... but I just don't like them. I always think there must be some way to do this without that.

Whatever. Again, thanks for your input.

I was a noob a decade ago asking questions that have been answered 1,000 times, just like new members today. It's people like you that got me to where I am today.

 

[nd0911]

Thank you for the answers and the nice discussion.
After examining the suggested solutions, I decided to go for Eric W's solution and adapted it to my needs.