Difference between revisions of "Recursive Functions"

From ACSL Category Descriptions
Jump to navigation Jump to search
(40 intermediate revisions by 2 users not shown)
Line 1: Line 1:
A definition that defines an object in terms of itself is said to be ''recursive''.  In computer science, recursion refers to a function or subroutine that calls itself, and it is
A definition that defines an object in terms of itself is said to be ''recursive''.  In computer science, recursion refers to a function or subroutine that calls itself, and it is
a fundamental paradigm in programming. A recursive program is used for solving problems that can be broken in sub-problems of the same type, doing so recursively until
a fundamental paradigm in programming. A recursive program is used for solving problems that can be broken down into sub-problems of the same type, doing so until
the problem is easy enough to solve directly.
the problem is easy enough to solve directly.
== Examples ==
=== Fibonacci Numbers ===
   
   
A common recursive function that you’ve probably encountered is the Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, and so on. That is, you get the next Fibonacci number by adding together the previous two. Mathematically, this is written as  
A common recursive function that you’ve probably encountered is the Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, and so on. That is, you get the next Fibonacci number by adding together the previous two. Mathematically, this is written as  
Line 7: Line 11:
$$f(N)=f(N-1)+f(N-2)$$
$$f(N)=f(N-1)+f(N-2)$$


Try finding F(8). No doubt, you have the correct answer, because you see that F(0)=0 and F(1) = 1. To be formal about this, we need to also define when the recursion stops, called the ''base cases''. In this case, $f(0)=1$, and $f(1)=1$. So, the correct definition of the Fibonacci numbers is:
Try finding f(10). No doubt, you have the correct answer, because you intuitively stopped when you reach $f(1)$ and $f(0)$.  
To be formal about this, we need to define when the recursion stops, called the ''base cases''.  
The base cases for the Fibonacci function is $f(0)=0$, and $f(1)=1$. The typical way to write this function is as follows:
$$f(N)=\cases{N & if $N \le 1$\cr
f(N-1)+f(N-2) & if $N > 1$}$$
 
Here is a Python implementation of the Fibonacci function:


$$f(N)=\cases{1 & if $N=0$\cr
::<syntaxhighlight lang="python">
1 & if $N=1$\cr
def Fibonacci(x):
f(N-1)+f(N-2) & if $N > 1$}$$
  if (x <= 1) return x
  return Fibonacci(x-1) + Fibonacci(x-2)
</syntaxhighlight>
 
(As a challenge to the reader: How could you implement the Fibonacci function without using recursion?)
 
=== Factorial Function ===


In computer science, we often use the term “recursion” to refer to a procedure (function, subroutine) whose implementation calls itself. Here is an implementation of the Fibonacci function:
Consider the factorial function, $n! = n * (n-1) * ... * 1$, with 0! defined as having a value of 1. We can define this recursively as follows:  


$$f(x)=\cases
{1 & if $x=0$\cr
x*f(x-1) & if $x\gt 0$\cr
}$$


With this definition, the factorial of every non-negative integer can be found.


::<syntaxhighlight lang="python">
Here is a Python implementation of the factorial function:
def Fibonacci(int x):
::<syntaxhighlight lang="python">def Factorial(x):
  if (x == 0) return 0
  if (x == 0) return 1
  if (x == 1) return 1
  return x * Factorial(x-1)
  return Fibonacci(x-1) + Fibonacci(x - 2
</syntaxhighlight>
</syntaxhighlight>


Consider the factorial function, $n!$ It is often defined as $1 * 2* 3 … * N-1 * N$, with 0! defined as have a value of 1. We can define this recursively as follows:
=== Some Definitions ===


$$f(x)=\cases{x*f(x-1) & if $x\gt 0$\cr
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.
1 & if $x=0$}$$


(It would have been probably to use $x\le 0$ rather than $x=0$ in the base case, to prevent the function from being undefined when $x$ is a negative number.)
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.


Here is a Python implementation of the factorial function:
== Sample Problems==
 
This ACSL category focuses on mathematical recursive functions rather than programming procedures; but you’ll see some of the latter.
You will  typically  be asked to evaluate a recursive function for some specific value. 
It's important that you are careful and neat.  Work  your  way  down  the  recursive  calls  until  there  are  no  more  calls,  and  then  work  your  way  back  up. 
=== Sample Problem 1 ===
 
'''Problem:''' Find $g(11)$ given the following
$$g(x)=\cases
{g(x-3)+1 & if $x>0$\cr
3x & otherwise\cr
}$$
 
'''Solution:'''
 
The evaluation proceeds top-down as follows:
 
$$\begin{align}
g(11)&=g(8)+1\cr
g(8)&=g(5)+1\cr
g(5)&=g(2)+1\cr
g(2)&=g(-1)+1\cr
g(-1)&=-3\cr
\end{align}$$
 
We now use what we know about $g(-1)$ to learn more values, working our way back "up" the recursion:
:We now know the value of $g(2): g(2)=-3+1=-2$
:We now know the value of $g(5): g(5)= -2+1=-1$
:We now know the value of $g(8): g(8) = -1+1=0$
:And finally, we now have the value of $g(11): g(11)=0+1=1$
 
=== Sample Problem 2 ===
 
'''Problem:''' Find the value of $h(13)$ given the following definition of $h$:
 
$$h(x)=\cases
{h(x-7)+1 & when $x>5$\cr
x & when $0 \le x \le 5$\cr
h(x+3) & when $x \lt 0$}$$
 
'''Solution:'''
 
$$\begin{align}
h(13) &= h(6)+1 & \text{top rule, since $x>5$}\cr
h(6) &= h(-1)+1 & \text{top rule, since $x>5$}\cr
h(-1)&= h(-1+3) =h(2)& \text{bottom rule, since $x<0$}\cr
h(2)&=2&\text{middle rule, since $0 \le x \le 5$}\cr
\end{align}$$
 
We now work our way back up the recursion, filling in values that have been computed.
 
:$h(-1) = h(2) = 2$
:$h(6)=h(-1)+1 = 2+1=3$
:$h(13)=h(6)+1= 3+1=4$
 
=== Sample Problem 3 ===
 
'''Problem:''' Find the value of $f(12,6)$ given the following definition of $f$:


::<syntaxhighlight lang="python">
$$f(x,y)=\cases
def Factorial(int x):
{f(x-y,y-1)+2 & when $x>y$\cr
  if (x<=0) return 1
x+y & otherwise}$$
  return x*Factorial(x-1)
</syntaxhighlight>


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. And multiple recursion, illustrated by the Fibonacci numbers, is when a function has multiple self references.
'''Solution:'''


The Sierpinski Triangle is an equilateral triangle, subdivided recursively into smaller equilateral triangles:
$$\begin{align}
f(12,6) &= f(6,5)+2 & \text{top rule, since $x>y$}\cr
f(6,5) &= f(1,4)+2 & \text{top rule, since $x>y$}\cr
f(1,4) &= 1+4 = 5& \text{bottom rule, since $x \le y$}\cr
\end{align}$$


We now work our way back up the recursion, filling in values that have been computed.


:$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:


In computer science, recursion is an important technique for solving problems: One divides a problem into subproblems of the same type, solves each, and combines the results. The breaking down into smaller pieces happens until some “base case” is reached. You often hear this called “divide and conquer”. To use that terminology, Fib(N) is solved by dividing it into Fib(N-1) and Fib(N-2), finding the results of each, and then combining the results by adding them together. Violla!
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.


Many beginning programmers have a real tough time understanding recursion; so if this is confusing to you, not to worry!
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?


In this ACSL category, we’ll focus on mathematical recursive functions rather than programming procedures; but you’ll see some of the latter, no doubt!
'''Solution:'''


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


== Online Resources ==
== Online Resources ==
Line 62: 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>
Line 83: 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]].
|}
|}


===Other Videos===
===Other Videos===


The follow YouTube videos cover various aspects of this topic; they were created by authors who are not involved (or aware) of ACSL, to the best of our knowledge. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.
Because recursion is such a fundamental concept in computer science, there is no end to the number of YouTube videos that cover the topic. There are dozens of walk-throughs of the factorial and Fibonacci functions, and of other classic algorithms such as Towers of Hanoi and Binary Trees.
Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.
 
{|
 
|-
| <youtube width="300" height="180">https://youtu.be/LdNdfPhwCP4</youtube>
| [https://youtu.be/LdNdfPhwCP4 ''Recursion lecture 1'' ('''anim aland''')]
 
Prof. Alan Dorin from Monash University presents an wonderful introduction to recursion. The last part of the video uses factorial as an example. Taken note how his base case guards against infinite recursion.
 
|-
| <youtube width="300" height="180">https://youtu.be/dxyYP3BSdcQ</youtube>
| [https://youtu.be/dxyYP3BSdcQ ''Fibonacci Sequence - Anatomy of recursion and space complexity analysis'' ('''mycodeschool''')]
 
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]. 
 
|}

Revision as of 06:23, 21 July 2020

A definition that defines an object in terms of itself is said to be recursive. In computer science, recursion refers to a function or subroutine that calls itself, and it is a fundamental paradigm in programming. A recursive program is used for solving problems that can be broken down into sub-problems of the same type, doing so until the problem is easy enough to solve directly.

Examples

Fibonacci Numbers

A common recursive function that you’ve probably encountered is the Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, and so on. That is, you get the next Fibonacci number by adding together the previous two. Mathematically, this is written as

$$f(N)=f(N-1)+f(N-2)$$

Try finding f(10). No doubt, you have the correct answer, because you intuitively stopped when you reach $f(1)$ and $f(0)$. To be formal about this, we need to define when the recursion stops, called the base cases. The base cases for the Fibonacci function is $f(0)=0$, and $f(1)=1$. The typical way to write this function is as follows: $$f(N)=\cases{N & if $N \le 1$\cr f(N-1)+f(N-2) & if $N > 1$}$$

Here is a Python implementation of the Fibonacci function:

def Fibonacci(x):
  if (x <= 1) return x
  return Fibonacci(x-1) + Fibonacci(x-2)

(As a challenge to the reader: How could you implement the Fibonacci function without using recursion?)

Factorial Function

Consider the factorial function, $n! = n * (n-1) * ... * 1$, with 0! defined as having a value of 1. We can define this recursively as follows:

$$f(x)=\cases {1 & if $x=0$\cr x*f(x-1) & if $x\gt 0$\cr }$$

With this definition, the factorial of every non-negative integer can be found.

Here is a Python implementation of the factorial function:

def Factorial(x):
  if (x == 0) return 1
  return x * Factorial(x-1)

Some Definitions

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

This ACSL category focuses on mathematical recursive functions rather than programming procedures; but you’ll see some of the latter. You will typically be asked to evaluate a recursive function for some specific value. It's important that you are careful and neat. Work your way down the recursive calls until there are no more calls, and then work your way back up.

Sample Problem 1

Problem: Find $g(11)$ given the following $$g(x)=\cases {g(x-3)+1 & if $x>0$\cr 3x & otherwise\cr }$$

Solution:

The evaluation proceeds top-down as follows:

$$\begin{align} g(11)&=g(8)+1\cr g(8)&=g(5)+1\cr g(5)&=g(2)+1\cr g(2)&=g(-1)+1\cr g(-1)&=-3\cr \end{align}$$

We now use what we know about $g(-1)$ to learn more values, working our way back "up" the recursion:

We now know the value of $g(2): g(2)=-3+1=-2$
We now know the value of $g(5): g(5)= -2+1=-1$
We now know the value of $g(8): g(8) = -1+1=0$
And finally, we now have the value of $g(11): g(11)=0+1=1$

Sample Problem 2

Problem: Find the value of $h(13)$ given the following definition of $h$:

$$h(x)=\cases {h(x-7)+1 & when $x>5$\cr x & when $0 \le x \le 5$\cr h(x+3) & when $x \lt 0$}$$

Solution:

$$\begin{align} h(13) &= h(6)+1 & \text{top rule, since $x>5$}\cr h(6) &= h(-1)+1 & \text{top rule, since $x>5$}\cr h(-1)&= h(-1+3) =h(2)& \text{bottom rule, since $x<0$}\cr h(2)&=2&\text{middle rule, since $0 \le x \le 5$}\cr \end{align}$$

We now work our way back up the recursion, filling in values that have been computed.

$h(-1) = h(2) = 2$
$h(6)=h(-1)+1 = 2+1=3$
$h(13)=h(6)+1= 3+1=4$

Sample Problem 3

Problem: Find the value of $f(12,6)$ given the following definition of $f$:

$$f(x,y)=\cases {f(x-y,y-1)+2 & when $x>y$\cr x+y & otherwise}$$

Solution:

$$\begin{align} f(12,6) &= f(6,5)+2 & \text{top rule, since $x>y$}\cr f(6,5) &= f(1,4)+2 & \text{top rule, since $x>y$}\cr f(1,4) &= 1+4 = 5& \text{bottom rule, since $x \le y$}\cr \end{align}$$

We now work our way back up the recursion, filling in values that have been computed.

$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:

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

Online Resources

ACSL

The following videos show the solution to problems that have appeared in previous ACSL contests.

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

Recursion Example 1 (CalculusNguyenify)

The video walks through the solution to a straight-forward single-variable recursive function, that is, $f(x)=\cases{....}$ The problem appeared in ACSL Senior Division Contest #1, 2014-2015.

Recursion Example 2 (CalculusNguyenify)

The video walks through the solution to a 2-variable recursive function, that is, $f(x,y)=\cases{....}$ . The problem appeared in ACSL Senior Division Contest #1, 2014-2015.

Recursive Functions ACSL Example Problem (Tangerine Code)

The video walks through the solution to a 2-variable recursive function, that is, $f(x,y)=\cases{....}$ .

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 [Part 2], [Part 3], and [Part 4].

Other Videos

Because recursion is such a fundamental concept in computer science, there is no end to the number of YouTube videos that cover the topic. There are dozens of walk-throughs of the factorial and Fibonacci functions, and of other classic algorithms such as Towers of Hanoi and Binary Trees. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.

Recursion lecture 1 (anim aland)

Prof. Alan Dorin from Monash University presents an wonderful introduction to recursion. The last part of the video uses factorial as an example. Taken note how his base case guards against infinite recursion.

Fibonacci Sequence - Anatomy of recursion and space complexity analysis (mycodeschool)

The video is hand-simulation on the whiteboard of the recursive code for computing a Fibonnaci number. The code uses a base case of if n<=1 return n to prevent infinite recursion where the function called with a negative parameter.

Towers of Hanoi (Arnaldo Pedro Figueira Figueira)

A nice explanation of the Towers of Hanoi from MIT edX Course: MITx: 6.00x Introduction to Computer Science and Programming.