Recursive Functions - Revision history

Marc: /* Other Videos */

2021-12-08T04:18:17Z

Marc: /* ACSL */

2021-12-08T04:17:53Z

ACSL

← Older revision		Revision as of 21:17, 7 December 2021
Line 184:		Line 184:
	The video walks through the solution to a 2-variable recursive function, that is, $f(x,y)=\cases{....}$ .		The video walks through the solution to a 2-variable recursive function, that is, $f(x,y)=\cases{....}$ .

	\|-
	~~\| <youtube width="300" height="180">https://youtu.be/BGCGlpm7Cow</youtube>~~
	~~\| [https://youtu.be/BGCGlpm7Cow ''ACSL Recursive Functions Part -1 by Ravi Yeluru'' ('''mesra''')]~~

	The first of 4 videos capturing Ravi Yeluru solving a handful of ACSL Recursive Function problems. Other videos are [[https://youtu.be/n5otUyH1j6A Part 2]], [[https://youtu.be/xHaHwNHlMj4 Part 3]], and [[https://youtu.be/vj2pvAL8tQQ Part 4]].
	\|}		\|}

Raj Joshi: /* ACSL */

2020-07-21T13:23:06Z

ACSL

← Older revision		Revision as of 06:23, 21 July 2020
Line 157:		Line 157:

	{\|		{\|
			\|-
			\| <youtube width="300" height="180">https://youtu.be/YinptBVZNFM</youtube>
			\| [https://youtu.be/YinptBVZNFM "ACSL Math: Recursive Functions" (Quick Coding Bytes)]

			This video introduces the topic, then using an example problem, explains the methodology to solve problems that appear on ACSL contests.

	\|-		\|-
	\| <youtube width="300" height="180">https://youtu.be/OjZSIXStSr8</youtube>		\| <youtube width="300" height="180">https://youtu.be/OjZSIXStSr8</youtube>

Marc Brown: /* ACSL */

2018-08-21T04:40:46Z

ACSL

← Older revision		Revision as of 21:40, 20 August 2018
Line 178:		Line 178:
	The video walks through the solution to a 2-variable recursive function, that is, $f(x,y)=\cases{....}$ .		The video walks through the solution to a 2-variable recursive function, that is, $f(x,y)=\cases{....}$ .

			\|-
			\| <youtube width="300" height="180">https://youtu.be/BGCGlpm7Cow</youtube>
			\| [https://youtu.be/BGCGlpm7Cow ''ACSL Recursive Functions Part -1 by Ravi Yeluru'' ('''mesra''')]

			The first of 4 videos capturing Ravi Yeluru solving a handful of ACSL Recursive Function problems. Other videos are [[https://youtu.be/n5otUyH1j6A Part 2]], [[https://youtu.be/xHaHwNHlMj4 Part 3]], and [[https://youtu.be/vj2pvAL8tQQ Part 4]].
	\|}		\|}

Carlen: /* Factorial Function */

2018-08-11T01:50:14Z

Factorial Function

← Older revision		Revision as of 18:50, 10 August 2018
Line 36:		Line 36:
	}$$		}$$

	With this definition, the factorial of a negative ~~number is not defined~~.		With this definition, the factorial of every non-negative integer can be found.

	Here is a Python implementation of the factorial function:		Here is a Python implementation of the factorial function:

Carlen: /* Sample Problem 4 */

2018-08-11T01:43:53Z

Sample Problem 4

← Older revision		Revision as of 18:43, 10 August 2018
Line 141:		Line 141:

	In the first pass, we get four squares of side 8.		In the first pass, we get four squares of side 8.
	One is painted; three are unpainted.		One is painted, three are unpainted.
	Next, we have 3*4 squares of side 4.		Next, we have 3*4 squares of side 4.
	Three are painted (area=3*42), nine are not.		Three are painted (area=3*4<sup>2</sup>), nine are not.
	Next, we have 9*4 squares of side 2.		Next, we have 9*4 squares of side 2.
	Nine are painted (area = 9*22), 27 are not.		Nine are painted (area = 9*2<sup>2</sup>), 27 are not.
	Finally, we have 27*4 squares of side 1.		Finally, we have 27*4 squares of side 1.
	Twenty-seven are painted.		Twenty-seven are painted.
	Therefore, the total painted is 18<sup>2</sup>+34<sup>2</sup>+92<sup>2</sup>+271<sup>2</sup> = 175.		Therefore, the total painted is 18<sup>2</sup> + 34<sup>2</sup> + 92<sup>2</sup> + 271<sup>2</sup> = 175.

	== Online Resources ==		== Online Resources ==

Carlen: /* Sample Problem 4 */

2018-08-11T01:39:46Z

Sample Problem 4

← Older revision		Revision as of 18:39, 10 August 2018
Line 130:		Line 130:
	'''Problem:''' Consider the following recursive algorithm for painting a square:		'''Problem:''' Consider the following recursive algorithm for painting a square:

	1. Given a square.~~\cr~~		1. Given a square.
	2. If the length of a side is less than 2 feet, then stop.~~\cr~~		2. If the length of a side is less than 2 feet, then stop.
	3. Divide the square into 4 equal size squares (i.e., draw a “plus” sign inside the square).~~\cr~~		3. Divide the square into 4 equal size squares (i.e., draw a “plus” sign inside the square).
	4. Paint one of these 4 small squares.~~\cr~~		4. Paint one of these 4 small squares.
	5. Repeat this procedure (start at step 1) for each of the 3 unpainted squares.~~\cr~~		5. Repeat this procedure (start at step 1) for each of the 3 unpainted squares.

	If this algorithm is applied to a square with a side of 16 feet (having a total area of 256 sq. feet), how many square feet will be painted?		If this algorithm is applied to a square with a side of 16 feet (having a total area of 256 sq. feet), how many square feet will be painted?
Line 140:		Line 140:
	'''Solution:'''		'''Solution:'''

	~~$$\begin{align}~~		In the first pass, we get four squares of side 8.
	In the first pass, we get four squares of side 8.~~\cr~~		One is painted; three are unpainted.
	One is painted; three are unpainted.~~\cr~~		Next, we have 3*4 squares of side 4.
	Next, we have 3*4 squares of side 4.~~\cr~~		Three are painted (area=3*42), nine are not.
	Three are painted (area=3*42), nine are not.~~\cr~~		Next, we have 9*4 squares of side 2.
	Next, we have 9*4 squares of side 2.~~\cr~~		Nine are painted (area = 9*22), 27 are not.
	Nine are painted (area = 9*22), 27 are not.~~\cr~~		Finally, we have 27*4 squares of side 1.
	Finally, we have 27*4 squares of side 1.~~\cr~~		Twenty-seven are painted.
	Twenty-seven are painted.~~\cr~~
	Therefore, the total painted is 18<sup>2</sup>+34<sup>2</sup>+92<sup>2</sup>+271<sup>2</sup> = 175.		Therefore, the total painted is 18<sup>2</sup>+34<sup>2</sup>+92<sup>2</sup>+271<sup>2</sup> = 175.
	~~\end{align}$$~~

	== Online Resources ==		== Online Resources ==

Carlen: /* Sample Problems */

2018-08-11T01:37:16Z

Sample Problems

← Older revision		Revision as of 18:37, 10 August 2018
Line 69:		Line 69:

	$$\begin{align}		$$\begin{align}
	g(11)&=g(8)+1 \cr		g(11)&=g(8)+1\cr
	g(8)&=g(5)+1 \cr		g(8)&=g(5)+1\cr
	g(5)&=g(2)+1\cr		g(5)&=g(2)+1\cr
	g(2)&=g(-1)+1\cr		g(2)&=g(-1)+1\cr
Line 130:		Line 130:
	'''Problem:''' Consider the following recursive algorithm for painting a square:		'''Problem:''' Consider the following recursive algorithm for painting a square:

	1. Given a square.		1. Given a square.\cr
	2. If the length of a side is less than 2 feet, then stop.		2. If the length of a side is less than 2 feet, then stop.\cr
	3. Divide the square into 4 equal size squares (i.e., draw a “plus” sign inside the square).		3. Divide the square into 4 equal size squares (i.e., draw a “plus” sign inside the square).\cr
	4. Paint one of these 4 small squares.		4. Paint one of these 4 small squares.\cr
	5. Repeat this procedure (start at step 1) for each of the 3 unpainted squares.		5. Repeat this procedure (start at step 1) for each of the 3 unpainted squares.\cr

	If this algorithm is applied to a square with a side of 16 feet (having a total area of 256 sq. feet), how many square feet will be painted?		If this algorithm is applied to a square with a side of 16 feet (having a total area of 256 sq. feet), how many square feet will be painted?

Carlen: /* Sample Problems */

2018-08-11T01:32:03Z

Sample Problems

← Older revision		Revision as of 18:32, 10 August 2018
Line 126:		Line 126:
	:$f(12,6) = f(6,5) + 2 = f(1,4) + 2 + 2 = 5 + 2 + 2 = 9$		:$f(12,6) = f(6,5) + 2 = f(1,4) + 2 + 2 = 5 + 2 + 2 = 9$

			=== Sample Problem 4 ===

			'''Problem:''' Consider the following recursive algorithm for painting a square:

			1. Given a square.
			2. If the length of a side is less than 2 feet, then stop.
			3. Divide the square into 4 equal size squares (i.e., draw a “plus” sign inside the square).
			4. Paint one of these 4 small squares.
			5. Repeat this procedure (start at step 1) for each of the 3 unpainted squares.

			If this algorithm is applied to a square with a side of 16 feet (having a total area of 256 sq. feet), how many square feet will be painted?

			'''Solution:'''

			$$\begin{align}
			In the first pass, we get four squares of side 8.\cr
			One is painted; three are unpainted.\cr
			Next, we have 3*4 squares of side 4.\cr
			Three are painted (area=3*42), nine are not.\cr
			Next, we have 9*4 squares of side 2.\cr
			Nine are painted (area = 9*22), 27 are not.\cr
			Finally, we have 27*4 squares of side 1.\cr
			Twenty-seven are painted.\cr
			Therefore, the total painted is 18<sup>2</sup>+34<sup>2</sup>+92<sup>2</sup>+271<sup>2</sup> = 175.
			\end{align}$$

	== Online Resources ==		== Online Resources ==

Carlen: /* Examples */

2018-08-11T01:23:09Z

Examples

@@ Line 42: / Line 42: @@
   if (x == 0) return 1
   return x * Factorial(x-1)
 </syntaxhighlight>
@@ Line 68: / Line 48: @@
 A few definitions: ''Indirection recursion'' is when a function calls another function which eventually calls the original function. For example, A calls B, and then, before function B exits, function A is called (either by B or by a function that B calls). ''Single recursion'' is recursion with a single reference to itself, such as the factorial example above. ''Multiple recursion'', illustrated by the Fibonacci number function, is when a function has multiple self references. ''Infinite recursion'' is a recursive function that never returns because it keeps calling itself. The program will eventually crash with an ''out of memory'' error message of some sort.
-This ACSL category focuses on mathematical recursive functions rather than programming procedures, but you’ll see some of the latter.
+This ACSL category focuses on mathematical recursive functions rather than programming algorithms.  While many mathematical functions can be done iteratively more efficiently than they can be done recursively, many algorithms in computer science must be written recursively.  The Tower of Hanoi which is referred to in one of the videos is a good example of this.  Another example is given in the sample problems below.
 == Sample Problems==

← Older revision		Revision as of 21:18, 7 December 2021
Line 206:		Line 206:
	The video is hand-simulation on the whiteboard of the recursive code for computing a Fibonnaci number. The code uses a base case of <syntaxhighlight lang="python" inline>if n<=1 return n</syntaxhighlight> to prevent infinite recursion where the function called with a negative parameter.		The video is hand-simulation on the whiteboard of the recursive code for computing a Fibonnaci number. The code uses a base case of <syntaxhighlight lang="python" inline>if n<=1 return n</syntaxhighlight> to prevent infinite recursion where the function called with a negative parameter.

	\|-
	~~\| <youtube width="300" height="180">https://youtu.be/rVPuzFYlfYE</youtube>~~
	~~\| [https://youtu.be/rVPuzFYlfYE ''Towers of Hanoi'' ('''Arnaldo Pedro Figueira Figueira''')]~~

	~~A nice explanation of the Towers of Hanoi from MIT edX Course: [https://www.edx.org/course/subject/computer-science MITx: 6.00x Introduction to Computer Science and Programming].~~

	\|}		\|}