Ben Nadel
On User Experience (UX) Design, JavaScript, ColdFusion, Node.js, Life, and Love.
I am the chief technical officer at InVision App, Inc - a prototyping and collaboration platform for designers, built by designers. I also rock out in JavaScript and ColdFusion 24x7.
Meanwhile on Twitter
Loading latest tweet...
Ben Nadel at CFUNITED 2008 (Washington, D.C.) with:

Ask Ben: Recursive Numeric Pyramid

By Ben Nadel on

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:


 
 
 

 
Numeric Pyramid Explained To Be Directly Proportional To Current Row Of Pyramid  
 
 
 

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

  • <!--- Get the max height of the numeric pyramid. --->
  • <cfset intHeight = 4 />
  •  
  • <!---
  • Loop over the number of rows that we want to display
  • in our numeric pyramid. This will start at negative
  • *height* and go to positive *height*. This will give
  • us ((height * 2) + 1) rows.
  • --->
  • <cfloop
  • index="intRow"
  • from="#-intHeight#"
  • to="#intHeight#"
  • step="1">
  •  
  • <!---
  • Loop over the number of columns in this row,
  • starting at zero.
  • --->
  • <cfloop
  • index="intCol"
  • from="0"
  • to="#(intHeight - Abs( intRow ))#"
  • step="1">
  •  
  • #intCol#
  •  
  • </cfloop>
  •  
  • <!--- Line break. --->
  • <br />
  •  
  • </cfloop>

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:

  • <cffunction
  • name="OutputPyramid"
  • access="public"
  • returntype="void"
  • output="true"
  • hint="Outputs the numeric pyramid.">
  •  
  • <!--- Define arguments. --->
  • <cfargument
  • name="TargetHeight"
  • type="numeric"
  • required="true"
  • hint="The max height of the numeric pyramid."
  • />
  •  
  • <cfargument
  • name="CurrentHeight"
  • type="numeric"
  • required="false"
  • default="0"
  • hint="The current height of the output pyramid."
  • />
  •  
  • <!--- Define the local scope. --->
  • <cfset var LOCAL = StructNew() />
  •  
  •  
  • <!---
  • Check to see if the current height is equal to the
  • target height. In that case, we are going to output
  • just one row.
  • --->
  • <cfif (ARGUMENTS.TargetHeight EQ ARGUMENTS.CurrentHeight)>
  •  
  • <!--- Simply output the row to max height. --->
  • <cfloop
  • index="LOCAL.Column"
  • from="0"
  • to="#ARGUMENTS.TargetHeight#"
  • step="1">
  •  
  • #LOCAL.Column#
  •  
  • </cfloop>
  •  
  • <br />
  •  
  • <cfelse>
  •  
  • <!---
  • Since we are not outputting the max height row, we
  • want to output TWO of the same column sets with a
  • recursive call in the middle.
  • --->
  •  
  • <!--- Output first row. --->
  • <cfloop
  • index="LOCAL.Column"
  • from="0"
  • to="#ARGUMENTS.CurrentHeight#"
  • step="1">
  •  
  • #LOCAL.Column#
  •  
  • </cfloop>
  •  
  • <br />
  •  
  • <!---
  • In between our two mirrow columns, we want to output
  • the middle content. These are the rows with heigher
  • columns (and eventually the one max row). To make
  • this recursive, make sure to re-call this method
  • with a larget current row.
  • --->
  • <cfset OutputPyramid(
  • TargetHeight = ARGUMENTS.TargetHeight,
  • CurrentHeight = (ARGUMENTS.CurrentHeight + 1)
  • ) />
  •  
  • <!--- Output second row (same as first). --->
  • <cfloop
  • index="LOCAL.Column"
  • from="0"
  • to="#ARGUMENTS.CurrentHeight#"
  • step="1">
  •  
  • #LOCAL.Column#
  •  
  • </cfloop>
  •  
  • <br />
  •  
  • </cfif>
  •  
  •  
  • <!--- Return out. --->
  • <cfreturn />
  • </cffunction>

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:

  • <!--- Output a numeric pyrmaid with max height of 4. --->
  • <cfset OutputPyramid( 4 ) />

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.

Tweet This Interesting post by @BenNadel - Ask Ben: Recursive Numeric Pyramid Thanks my man — you rock the party that rocks the body!


Looking For A New Job?

100% of job board revenue is donated to Kiva. Loans that change livesFind out more »

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>

Reply to this Comment

@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).

Reply to this Comment

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>

Reply to this Comment

@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 :)

Reply to this Comment

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>

Reply to this Comment

@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>

Reply to this Comment

@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!

Reply to this Comment

@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.

Reply to this Comment

@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).

Reply to this Comment

Post A Comment

You — Get Out Of My Dreams, Get Into My Comments
Live in the Now
Oops!
Comment Etiquette: Please do not post spam. Please keep the comments on-topic. Please do not post unrelated questions or large chunks of code. And, above all, please be nice to each other - we're trying to have a good conversation here.