# Challenge: Recursive Recluse

• (2 Pages)
• 1
• 2

## 22 Replies - 12136 Views - Last Post: 16 September 2013 - 09:09 AM

• MrCupOfT

Reputation: 2262
• Posts: 9,462
• Joined: 29-May 08

# Challenge: Recursive Recluse

Posted 11 September 2013 - 10:59 AM

Challenge: Recursive Recluse

The recursive function is often seen as the bogey-man of programming.

Challenge

So your challenge is to slay that beast by not only writing a recursive function, but also writing an informative explanation for a learner to understand it.

The more unusual use of a recursive function, to solve a problem the better.

This post has been edited by AdamSpeight2008: 11 September 2013 - 11:02 AM

Is This A Good Question/Topic? 0

## Replies To: Challenge: Recursive Recluse

### #2 modi123_1

• Suitor #2

Reputation: 9195
• Posts: 34,516
• Joined: 12-June 08

## Re: Challenge: Recursive Recluse

Posted 11 September 2013 - 11:14 AM

Wait.. is this just a metaphorical beast, or should I incorporate that in my function?

```FUNCTION  SlayBeast()
IF beast exists THEN
attack()
SlayBeast()
ELSE
dance()
END IF
END FUNCTION

```

### #3 Witchking

Reputation: 68
• Posts: 188
• Joined: 17-February 13

## Re: Challenge: Recursive Recluse

Posted 11 September 2013 - 02:00 PM

Count the number of nodes in a tree.

```Function NumberOfNodes(node As Node) as Integer
Dim i As Integer = 1 'this node

For Each n As Node In node.Children
i += NumberOfNodes(n) 'count the nodes in each child tree
Next

Return i
End Function

Class Node

Public Property Children As IEnumerable(Of Node)

End Class
```

Spoiler

First time touching VB.. The syntax hurts :<

• MrCupOfT

Reputation: 2262
• Posts: 9,462
• Joined: 29-May 08

## Re: Challenge: Recursive Recluse

Posted 11 September 2013 - 02:37 PM

Witchking A big to trying a new programming language.
What language were you using previously?

VB.net is not that bad. I reimplemented your example using Sum
```Function NumberOfNodes( node As Node ) As Integer
Return node.Children.Sum(Function( ChildNode ) NumberOfNodes( ChildNode )) + 1
' Node has no child node then Sum() returns 0
' The + 1 is used to include in the count the node being referred in the input parameter (node)
End Function

```

This post has been edited by andrewsw: 11 September 2013 - 02:44 PM
Reason for edit:: not that bad :)

### #5 andrewsw

• Fire giant boob nipple gun!

Reputation: 3460
• Posts: 11,727
• Joined: 12-December 12

## Re: Challenge: Recursive Recluse

Posted 11 September 2013 - 02:44 PM

This is more instructional than clever:

```Option Strict On
Module Module1

Sub Main()
Dim iFind As Integer
Console.WriteLine("Enter a number between 1 and 100?")

FindTheNumber(iFind, 1, 100)
Console.WriteLine("Press ANY key")
End Sub

Sub FindTheNumber(ByVal value As Integer, _
ByVal bottom As Integer, ByVal top As Integer)
Dim mid As Integer

'guess the mid-point between bottom and top..
mid = CInt(bottom + (top - bottom) / 2)
'initially, this will be 50
If value = mid Then
Console.WriteLine("Found it: {0}", mid)
'the exit point for the recursive calls/recursion
'This MUST be reached at some point,
'otherwise the sequence (recursion) will never finish!
ElseIf value < mid Then
Console.WriteLine("It's less than {0}", mid)
'recursive call:
FindTheNumber(value, bottom, mid)
'moves the top-value half-way towards bottom
Else
Console.WriteLine("It's greater than {0}", mid)
'recursive call:
FindTheNumber(value, mid, top)
'moves the bottom-value half-way towards top
End If
End Sub
End Module
```

This post has been edited by andrewsw: 11 September 2013 - 11:20 PM

### #6 Witchking

Reputation: 68
• Posts: 188
• Joined: 17-February 13

## Re: Challenge: Recursive Recluse

Posted 11 September 2013 - 02:53 PM

I mostly do C#. I find the C style syntax much clearer and more understandable.

Quote

VB.net is that bad

Quote

Reason for edit:: not that bad

Maybe he meant it.

### #7 mojo666

Reputation: 352
• Posts: 771
• Joined: 27-June 09

## Re: Challenge: Recursive Recluse

Posted 11 September 2013 - 03:04 PM

Simple illustrative example
```'Sum Of First n Numbers returns 1+2+...+(n-1)+n
'Put another way, we can say it returns the sum of first (n-1) numbers + n
'Thus the following recursive code
Function SumOfFirstNumbers(n as int)
IF n<1 THEN
RETURN 0
ELSE
RETURN SumOfFirstNumbers(n-1) + n
END IF
END FUNCTION
```

The downside is people looking at such trivial examples will come to the conclusion "I will just be able to use loops instead".

• MrCupOfT

Reputation: 2262
• Posts: 9,462
• Joined: 29-May 08

## Re: Challenge: Recursive Recluse

Posted 11 September 2013 - 03:19 PM

It would be great to see a few more harder to understand examples.

In which case i shall set an additional challenge.

Recursion Challenge
Assume that the braces { } are correctly balanced, in a string.
Given the string and the position of a brace (either opening or closing), return the position of the balancing brace. No external variable usage; Defining variables inside the function is OK and so is input parameters. Nothing else is. Ie no globals.

This post has been edited by AdamSpeight2008: 11 September 2013 - 03:24 PM

### #9 Witchking

Reputation: 68
• Posts: 188
• Joined: 17-February 13

## Re: Challenge: Recursive Recluse

Posted 11 September 2013 - 03:20 PM

@mojo666 Perhaps not the best example, when one could use n(n+1)/2 instead.

For me what really drove home the concept of recursion was the merge sort algorithm, and the divide & conquer paradigm.

• MrCupOfT

Reputation: 2262
• Posts: 9,462
• Joined: 29-May 08

## Re: Challenge: Recursive Recluse

Posted 11 September 2013 - 03:32 PM

Challenge
Or if you feeling brave (or stupid), implement versions of the algorithms that appear in this thread with improved big O() values.
Eg NumberOfNodes is O(n2) can it be O(n) or even O( Log N ) ?

But you should state (or link to) which post you are challenging on and improving. The requirement for an explanation still stands.
Cos we are Mentor Ninjas.

This post has been edited by AdamSpeight2008: 11 September 2013 - 03:35 PM
Reason for edit:: Pesky edit cockroach bug />

### #11 mojo666

Reputation: 352
• Posts: 771
• Joined: 27-June 09

## Re: Challenge: Recursive Recluse

Posted 11 September 2013 - 03:39 PM

Witchking, on 11 September 2013 - 11:20 PM, said:

@mojo666 Perhaps not the best example, when one could use n(n+1)/2 instead. />/>

For me what really drove home the concept of recursion was the merge sort algorithm, and the divide & conquer paradigm.

I believe you have to demonstrate concepts in steps, though. Something like mergesort is better for demonstrating the usefulness of recursion after the person is comfortable with the concept as it is more difficult to implement such an algorithm iteratively. But, if the goal is to get people familiar with recursion, it is best to use familiar examples, even if recursion is not ideal for such examples. Summation is very familiar, and with things like summation notation, many people have even likely already used mathematical recursion without even knowing it. Thus it can be an ideal example to connect the dots in the learner's mind.

### #12 Witchking

Reputation: 68
• Posts: 188
• Joined: 17-February 13

## Re: Challenge: Recursive Recluse

Posted 12 September 2013 - 05:36 AM

AdamSpeight2008, on 12 September 2013 - 12:19 AM, said:

It would be great to see a few more harder to understand examples.

In which case i shall set an additional challenge.

Recursion Challenge
Assume that the braces { } are correctly balanced, in a string.
Given the string and the position of a brace (either opening or closing), return the position of the balancing brace. No external variable usage; Defining variables inside the function is OK and so is input parameters. Nothing else is. Ie no globals.

```const string Brackets = "{}";

int BalancingBracket(string s, int pos)
{
int br = Brackets.IndexOf(s[pos]);

pos -= br - (br + 1) % 2;

while (s[pos] != Brackets[(br + 1) % 2])
{
if (s[pos] == Brackets[br])
pos = BalancingBracket(s, pos);

pos -= br - (br + 1) % 2;
}

return pos;
}
```

### #13 andrewsw

• Fire giant boob nipple gun!

Reputation: 3460
• Posts: 11,727
• Joined: 12-December 12

## Re: Challenge: Recursive Recluse

Posted 12 September 2013 - 11:44 AM

Witchking that VB.NET is a bit curly

### #14 Witchking

Reputation: 68
• Posts: 188
• Joined: 17-February 13

## Re: Challenge: Recursive Recluse

Posted 12 September 2013 - 11:57 AM

andrewsw, on 12 September 2013 - 08:44 PM, said:

Witchking that VB.NET is a bit curly

So it is, but while i abhor the VB.NET syntax i thought the challenge interesting. And it's still .NET so it's close enough, i hope.

Spoiler

This post has been edited by Witchking: 12 September 2013 - 11:57 AM

• MrCupOfT

Reputation: 2262
• Posts: 9,462
• Joined: 29-May 08

## Re: Challenge: Recursive Recluse

Posted 13 September 2013 - 04:21 AM

Witchking Fails on a points.

Quote

No external variable usage

Spoiler