advanced recursiveness 1

[snotmare]

Hah, I'm not sure if recursiveness is a word, but it's the best I could come up with .

Most of us know about the popular recursive example of searching through file folders. Does anyone have any recursive examples that are a bit more complicated than this? I don't really have any coding problems that I need solutions for, but I was hoping to broaden my knowledge of recursiveness by seeing what others have done. If you don't mind sharing, please try to keep the code clean so it can be understood .

Thanks all!

He who has knowledge spares his words, and a man of understanding is of a calm spirit. Even a fool is counted wise when he holds his peace; when he shuts his lips, he is considered perceptive. - King Solomon

 

[strongm]

Here, let me google for you:

http://www.cs.uleth.ca/~cheng/courses/cs2620/slides/recursion-4up.pdf

 

[snotmare]

Yes, thank you. I was hoping for some ADVANCED techniques, but I do appreciate your response! No one here has used recursiveness to accomplish something a bit more complicated than file searches and factorials?

He who has knowledge spares his words, and a man of understanding is of a calm spirit. Even a fool is counted wise when he holds his peace; when he shuts his lips, he is considered perceptive. - King Solomon

 

[EBGreen]

I don't understand. What do you mean by advanced techniques? Recursion just means that a function calls itself. How complicated can that get?

[red]"... isn't sanity really just a one trick pony anyway?! I mean, all you get is one trick, rational thinking, but when you are good and crazy, oooh, oooh, oooh, the sky is the limit!" - The Tick[/red]

 

[snotmare]

Yah, I can see where there would be confusion with my post.

I once wrote a recursive routine that had different "states" if you will. The first time through, it would perform one function, and possibly change a flag to indicate what state the routine was in. The next time through, the routine would execute some different code depending on this "state" flag. Then within the recursive routine, it would then call a separate recursive routine if needed. It was fun to write, but complicated.

I would consider this kind of code a bit more complicated than your simple file search routine, but far from the most complicated routine I'm sure. I was hoping to see what you experts out there have written, hoping to pick up on some nifty techniques. That's all .

He who has knowledge spares his words, and a man of understanding is of a calm spirit. Even a fool is counted wise when he holds his peace; when he shuts his lips, he is considered perceptive. - King Solomon

 

[EBGreen]

Here is some code that I wrote to display complex data structures:

Option Explicit
Dim oDic
Dim arrTest
Dim oTemp
Dim oTemp2

Set oDic = CreateObject("Scripting.Dictionary")
oDic.Add "String", "Test"
oDic.Add "Bool", True
oDic.Add "Int", 1
arrTest = Array("1", "2")
oDic.Add "Array", arrTest
Set oTemp = CreateObject("Scripting.Dictionary")
oTemp.Add "First", "One"
oTemp.Add "Second", "Two"
oDic.Add "Dictionary", oTemp
Set oTemp = Nothing
Set oTemp2 = CreateObject("Scripting.Dictionary")
otemp2.add "Uno", 1
otemp2.Add "Dos", 2

oDic("Dictionary").Add "secondDic", oTemp2
oDIc("Dictionary")("secondDic").Add "Tres", 3
WScript.Echo oDIc("Dictionary")("secondDic")("Tres")

ShowDic oDic, "oDic", 0

Sub ShowDic(oD, strName, Indent)
	Dim strSpace
	Dim strKey
	strSpace = Space(Indent * 4)
	For Each strKey In oD.Keys()
		Select Case TypeName(oD.Item(strKey))
			Case "Integer" 
				WScript.Echo strSpace & strName & "(" & strKey & ") => " & oD.Item(strKey)
			Case "String"
				WScript.Echo strSpace & strName & "(" & strKey & ") => " & oD.Item(strKey)
			Case "Boolean"
				WScript.Echo strSpace & strName & "(" & strKey & ") => " & oD.Item(strKey)
			Case "Variant()"
				ShowArray oD.Item(strKey), strKey, Indent + 1
			Case "Dictionary"
				ShowDic od.Item(strKey), strKey, Indent + 1
			Case Else
				WScript.Echo "UNKNOWN TYPE: " & TypeName(od.Item(strKey)) & " " & strName & "(" & strKey & ") => " & oD.Item(strKey)
		End Select
	Next
End Sub

Sub ShowArray(oA, strName, Indent)
	Dim strSpace
	Dim  i
	strSpace = Space(Indent * 4)
	For i = 0 To UBound(oA)
		Select Case TypeName(oA(i))
			Case "Integer" 
				WScript.Echo strSpace & strName & "(" & i & ") => " & oA(i)
			Case "String"
				WScript.Echo strSpace & strName & "(" & i & ") => " & oA(i)
			Case "Boolean"
				WScript.Echo strSpace & strName & "(" & i & ") => " & oA(i)
			Case "Variant()"
				ShowArray oA(i), strName & "(" & i & ")", Indent + 1
			Case "Dictionary"
				ShowDic oA(i), strName & "(" & i & ")", Indent + 1
			Case Else
				WScript.Echo "UNKNOWN TYPE: " & TypeName(od.Item(strKey)) & " " & strName & "(" & strKey & ") => " & oD.Item(strKey)
		End Select
	Next
End Sub

[red]"... isn't sanity really just a one trick pony anyway?! I mean, all you get is one trick, rational thinking, but when you are good and crazy, oooh, oooh, oooh, the sky is the limit!" - The Tick[/red]

 

[snotmare]

Nice, thank you!

He who has knowledge spares his words, and a man of understanding is of a calm spirit. Even a fool is counted wise when he holds his peace; when he shuts his lips, he is considered perceptive. - King Solomon

 

[Sheco]

If you are just looking for other examples of useful recursion then do a google search for binary search trees.

Another example of useful recursion might be calculating all of the permissions that a particular user has in the Active Directory. A user will have some permissions based solely on the user account, and other permissions based on the account's membership in various groups. Once you start writing the code for handling the fact that groups themselves may be members of other groups you get to a place where recursion's usefulness becomes clear.

 

[mrmovie]

yes, good point Sheco, a classic problem is 'does a user have admin rights to a local machine'
other than checking if one can write to a root registry key one needs to loop through all nested group membership local and domain in the local admin group!

 

[strongm]

>something a bit more complicated than file searches and factorials?

Erm, well I think that solving the Tower of Hanoi and playing tic tac toe are reasonably advanced uses of recursion. I guess your definition differs