Ask Ben: Recursive Numeric Pyramid

Posted December 11, 2007 at 8:39 AM

Tags: ColdFusion, Ask Ben

Can you help me to find solution of this question by the recursion just print on the screen:

0
0 1
0 1 2
0 1 2 3
0 1 2 3 4
0 1 2 3
0 1 2
0 1
0

Thanx alot and help me to understand recursion very well. Thanx alot.

I am glad that this particular question was asked because this is not necessarily a case where recursion is the best answer. When you're learning recursion, just as when you learn anything new, you start to see it as solution to problems that don't necessarily need it. Sometimes that's because recursion just feels right; sometimes that's because patterns in problems are just straight-up hard to see.

In this case, the pattern is that the height of each row (number of columns in that row) is directly related to the difference between the max height and the absolute value of the current row when placed on a graph where the max row falls on the (y=0) axis. To better see this, take a look at this graphic:

With that in mind, this problem can be solved using two nested FOR loops:

 Launch code in new window » Download code as text file »

As you can see, we just loop from -intHeight to intHeight and output each appropriate column. This has a very linear execution path to it and it is completely scalable and will work no matter what the max height of the pyramid is.

That being said, you can also solve this problem using recursion, but you will quickly see that the recursive method has a lot more overhead in terms of both code and general logic. When it comes to recursion, one aspect of it can be thought of as a divide and conquer problem; for each iteration, we are solving a small part of the problem and then handing off the rest of it to be solved separately by the same function.

With that in mind, what is the divide and conquer approach to a pyramid? When I look at it, I see a mirror image reflected around the row with the max height. Taking that and extrapolating it to a divide and conquer approach, we want to output the smallest rows (top 0 and bottom 0) and then output everything in between those two rows. As we output everything between those two rows, we are going to output the top 0-1 row and the bottom 0-1 row and then everything in between those two rows... and so on and so forth until we hit our point of reflection - the max row.

Let's take that idea and wrap it up in a recursive function:

 Launch code in new window » Download code as text file »

As you can see, in our function we have two cases: either we are outputting the max row or we are outputting the two smaller columns on either side of the max row. Remember, it is essential to have logic in your recursive function that allows it to eventually execute without re-invoking itself. In our case, that scenario is the max row output. Notice that when we output the max row, we do not re-invoke the OutputPyramid() function. It is only when we are outputting the smaller rows that we re-execute the OutputPyramid() method to output the content between the two smaller rows.

Once we have this recursive function in place, we simply need to invoke it with the target height of the numeric pyramid:

 Launch code in new window » Download code as text file »

Since the current row height defaults to 0, that will be implied in our launch code.

Not only is there much more code involved in the recursive solution to this problem, there is also a lot of duplicate logic. We have three FOR loops; two of which do the exact same thing (output the smaller rows) but all three of them perform pretty much the same task - output from 0 to a specified height. There is a way to consolidate much of the code, but then you pretty much end up re-creating the original solution wrapped up in the overhead of a recursive function. So, recursion is an awesome thing, but certainly, not always the best option.

Download Code Snippet ZIP File

Post Comment  |  Ask Ben  |  Permalink  |  Other Searches  |  Print Page

• Add To Del.icio.us
• Add To Digg
• Add to Spurl.net
• Add to Wists
• Add to Simpy
• Add to Newsvine
• Add to BlinkList
• Add to Furl
• Add to reddit
• Add to FARK
• Add to BlogMarks
• Add to Yahoo! My Web
• Add to smarking
• Add to Ma.gnolia
• Add to Segnalo

Reader Comments

Hi Ben,

Here is another take, which only needs one loop:

<!--- set up our variables ---->
<cfset pSize = 4>
<cfset currNum = 0>
<cfset retString = ''>
<cfset pyramid = ''>

<!--- Here is our recursive function --->
<cffunction name='buildPyramid' returntype="string">
<cfargument name="pDir" type="string" required="true">
<cfloop from=0 to=#currNum# index='x'>
<cfset retString = "#retString# #x#">
</cfloop>
<cfset retString = "#retString#<br>">
<cfif currNum LT pSize AND pDir EQ 'up'>
<cfset currNum = currNum + 1>
<cfset pyramid = buildPyramid('up')>
<cfelseif currNum GT 0>
<cfset currNum = currNum - 1>
<cfset pyramid = buildPyramid('down')>
</cfif>
<cfreturn retString>
</cffunction>

<!--- call the function --->
<cfset pyramid = buildPyramid('up')>
<!--- output the result --- >
<cfoutput>#pyramid#</cfoutput>

@Gus,

Good stuff. Even with one loop, though, I think we see that the non-recursive solution is more simplistic. Also, I would try to pass variables through with the method calls rather than refer to global variables (that just makes me feel a bit uncomfortable).

OK, I had to try :)

No loops, recursion only (perhaps not completely the best method, but appears to work correctly) and I had to use the dreaded...*evaluate* :D BTW, this sounded quite a bit like a homework assignment, but I quite enjoyed the small challend.

<cffunction name="recurse" access="remote" output="true" returntype="void">
<cfargument name="currentValue" default="0" type="numeric" />
<cfargument name="maxValue" default="4" type="numeric" />
<cfargument name="direction" default="+" type="string" />
<cfargument name="arrayValue" default="#arrayNew(1)#" type="array" />

<cfif arguments.currentValue gt -1>
<cfif arguments.direction is "+">
<cfset arrayAppend(arguments.arrayValue, arguments.currentValue)>
<cfelseif arrayLen(arguments.arrayValue)>
<cfset arrayDeleteAt(arguments.arrayValue, arrayLen(arguments.arrayValue))>
</cfif>
<cfoutput>#ArrayToList(arguments.arrayValue, " ")#</cfoutput><br>
<cfif arguments.currentValue eq arguments.maxValue>
<cfset arguments.direction = "-">
</cfif>
<cfset recurse(Evaluate("arguments.currentValue" & arguments.direction & "1"), arguments.maxValue, arguments.direction, arguments.arrayValue) >
</cfif>

</cffunction>

@Gareth,

Nicely done. I like how you are using the direction variable to work also as a mathematical operator. As far as the Evaluate() goes, you can actually do that without using it:

Evaluate("arguments.currentValue" & arguments.direction & "1")

... can simply be:

arguments.currentValue + "#arguments.direction#1"

In this case, you are creating a string form of a number (+1 or -1) and then adding that to the currentValue. ColdFusion will convert the string to a number for you (in theory - I have not tested).

Yeah, it did feel like a homework question :)

Here's my take. Comments are welcome.

<cfscript>
min = 0;
max = 4;

// code: http://shayne.pastebin.com/f9f28c41
myCounter = CreateObject("component", "Counter").init(min,max);
myCounter.setDelimiter(" ");

for (i=min; i <= max; ++i) {
myCounter.setEndNum(max-i);
WriteOutput(myCounter.run() & "<br />");
}

for (i=min+1; i <= max; ++i) {
myCounter.setEndNum(i);
WriteOutput(myCounter.run() & "<br />");
}
</cfscript>

@Shayne,
Geez that's a lot of code :) Not sure that the extra overhead for creating the object would be worth it, but the way you've written it is definitely a lot more extensible than mine would be :)

I managed to revise the code slightly and get rid of my evaluate completely

<cffunction name="recurse" access="remote" output="true" returntype="void">
<cfargument name="direction" default="+" type="string" />
<cfargument name="arrayValue" default="#arrayNew(1)#" type="array" />

<cfset var maxValue = 5 />

<cfif arguments.direction is "+">
<cfset arrayAppend(arguments.arrayValue, arrayLen(arguments.arrayValue))>
<cfelseif arrayLen(arguments.arrayValue)>
<cfset arrayDeleteAt(arguments.arrayValue, arrayLen(arguments.arrayValue))>
</cfif>

<cfif arrayLen(arguments.arrayValue)>
<cfoutput>#ArrayToList(arguments.arrayValue, " ")#</cfoutput><br>
<cfif arrayLen(arguments.arrayValue) eq maxValue>
<cfset arguments.direction = "-">
</cfif>
<cfset recurse(arguments.direction, arguments.arrayValue) >
</cfif>

</cffunction>

@Gareth

Yeah - I took a different approach to the problem. Not so say which is better, faster, stronger, etc... (daft punk anyone?).

Warning! My opinion: I don't think the few milliseconds it takes to create the object would warrant the need to implement something procedurally, inline. I'm sure there are a few situations that would favor something procedural - in regards to speed. Given the amount of re-usability and maintainability OO designs offer - I tend to look in that direction. You never know when you might need to generate a linear numeric sequence!

@Shayne,

Cool take on it. I like that you package up the row building logic into the CFC.

@Gareth,

Way to get rid of the Evaluate; more than that, though, that seems like a cleaner solution. The one minor note - if you have have output="true" in your CFFunction tag, you don't need the CFOutput tags.

Good stuff.

@Ben,
I've never tried leaving out the cfoutput tags when setting output="true". Nice!

@Gareth,

No problem. Yeah, when you define the function tag as being output, the whole body of the function acts as though it were inside a CFOutput tag (like being inside CFMail).

Post Comment  |  Ask Ben

Post A Comment

Please review the following issues:

Author Name:
Author Email:
Author Website:
Comment:	Formatting: <strong>bold</strong> <em>italic<em>
	Remember my information
	Subscribe to entry *
	Send me a copy of this comment (as part of the comment thread)

 

* If you subscribe, any new posts to this thread will be sent to your email address.