Can you help me to find solution of this question by the recursion just print on the screen:
0 1 2
0 1 2 3
0 1 2 3 4
0 1 2 3
0 1 2
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:
<!--- 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.
Want to use code from this post? Check out the license.