Challenge: Recursive Recluse

  • (2 Pages)
  • +
  • 1
  • 2

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

#1 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2216
  • View blog
  • Posts: 9,352
  • Joined: 29-May 08

Challenge: Recursive Recluse

Post icon  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  Icon User is offline

  • Suitor #2
  • member icon



Reputation: 8374
  • View blog
  • Posts: 31,122
  • 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




Posted Image
Was This Post Helpful? 1
  • +
  • -

#3 Witchking  Icon User is offline

  • D.I.C Head

Reputation: 68
  • View blog
  • Posts: 186
  • 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 :<
Was This Post Helpful? 1
  • +
  • -

#4 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2216
  • View blog
  • Posts: 9,352
  • 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 :)

Was This Post Helpful? 0
  • +
  • -

#5 andrewsw  Icon User is offline

  • Fire giant boob nipple gun!
  • member icon

Reputation: 2884
  • View blog
  • Posts: 9,566
  • 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?")
        iFind = CInt(Console.ReadLine())

        FindTheNumber(iFind, 1, 100)
        Console.WriteLine("Press ANY key")
        Console.ReadKey()
    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

Was This Post Helpful? 1
  • +
  • -

#6 Witchking  Icon User is offline

  • D.I.C Head

Reputation: 68
  • View blog
  • Posts: 186
  • 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. :rolleyes2:
Was This Post Helpful? 0
  • +
  • -

#7 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 337
  • View blog
  • Posts: 730
  • 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".
Was This Post Helpful? 0
  • +
  • -

#8 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2216
  • View blog
  • Posts: 9,352
  • 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

Was This Post Helpful? 0
  • +
  • -

#9 Witchking  Icon User is offline

  • D.I.C Head

Reputation: 68
  • View blog
  • Posts: 186
  • 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.
Was This Post Helpful? 0
  • +
  • -

#10 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2216
  • View blog
  • Posts: 9,352
  • Joined: 29-May 08

Re: Challenge: Recursive Recluse

Posted 11 September 2013 - 03:32 PM

:shuriken: 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. :smartass: :shuriken:

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

Was This Post Helpful? 0
  • +
  • -

#11 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 337
  • View blog
  • Posts: 730
  • Joined: 27-June 09

Re: Challenge: Recursive Recluse

Posted 11 September 2013 - 03:39 PM

View PostWitchking, 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.
Was This Post Helpful? 0
  • +
  • -

#12 Witchking  Icon User is offline

  • D.I.C Head

Reputation: 68
  • View blog
  • Posts: 186
  • Joined: 17-February 13

Re: Challenge: Recursive Recluse

Posted 12 September 2013 - 05:36 AM

View PostAdamSpeight2008, 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;
}

Was This Post Helpful? 1
  • +
  • -

#13 andrewsw  Icon User is offline

  • Fire giant boob nipple gun!
  • member icon

Reputation: 2884
  • View blog
  • Posts: 9,566
  • Joined: 12-December 12

Re: Challenge: Recursive Recluse

Posted 12 September 2013 - 11:44 AM

Witchking that VB.NET is a bit curly ;)
Was This Post Helpful? 0
  • +
  • -

#14 Witchking  Icon User is offline

  • D.I.C Head

Reputation: 68
  • View blog
  • Posts: 186
  • Joined: 17-February 13

Re: Challenge: Recursive Recluse

Posted 12 September 2013 - 11:57 AM

View Postandrewsw, 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

Was This Post Helpful? 1
  • +
  • -

#15 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2216
  • View blog
  • Posts: 9,352
  • 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

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2