Difference between revisions of "Recursive Functions"

From ACSL Category Descriptions
Jump to: navigation, search
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)=1$, and $f(1)=1$. The typical way to write this function is as follows:
 
$$f(N)=\cases{1 & if $N=0$\cr
 
$$f(N)=\cases{1 & if $N=0$\cr
 
1 & if $N=1$\cr
 
1 & if $N=1$\cr
 
f(N-1)+f(N-2) & if $N > 1$}$$
 
f(N-1)+f(N-2) & if $N > 1$}$$
  
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:
+
Here is a Python implementation of the Fibonacci function:
 
+
 
+
  
 
::<syntaxhighlight lang="python">
 
::<syntaxhighlight lang="python">
def Fibonacci(int x):
+
def Fibonacci(x):
 
  if (x == 0) return 0
 
  if (x == 0) return 0
 
  if (x == 1) return 1
 
  if (x == 1) return 1
  return Fibonacci(x-1) + Fibonacci(x - 2
+
  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:  
+
(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 have a value of 1. We can define this recursively as follows:  
  
 
$$f(x)=\cases{x*f(x-1) & if $x\gt 0$\cr
 
$$f(x)=\cases{x*f(x-1) & if $x\gt 0$\cr
 
1 & if $x=0$}$$
 
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.)
+
WIth this definition, the factorial of a negative number is not defined.  
  
 
Here is a Python implementation of the factorial function:
 
Here is a Python implementation of the factorial function:
  
 
::<syntaxhighlight lang="python">  
 
::<syntaxhighlight lang="python">  
def Factorial(int x):
+
def Factorial(x):
 
  if (x<=0) return 1
 
  if (x<=0) return 1
 
  return x*Factorial(x-1)
 
  return x*Factorial(x-1)
 
</syntaxhighlight>
 
</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.  
+
In the implementation above, the base case is listed as <syntaxhighlight lang="python"> x <= 0</syntaxhighlight> rather than <syntaxhighlight lang="python"> x < 0</syntaxhighlight> 
 +
to return a value 1 when called with a negative number. Had the implementation been coded with ''<'', then calling it with a negative number would lead the function never returning. This is called ''infinite recursion''.  
  
The Sierpinski Triangle is an equilateral triangle, subdivided recursively into smaller equilateral triangles:
+
=== 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.
  
  
  
  
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!
 
  
 
Many beginning programmers have a real tough time understanding recursion; so if this is confusing to you, not to worry!
 
Many beginning programmers have a real tough time understanding recursion; so if this is confusing to you, not to worry!

Revision as of 02:47, 1 August 2018

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)=1$, and $f(1)=1$. The typical way to write this function is as follows: $$f(N)=\cases{1 & if $N=0$\cr 1 & if $N=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 == 0) return 0
  if (x == 1) return 1
  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 have a value of 1. We can define this recursively as follows:

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

WIth this definition, the factorial of a negative number is not defined.

Here is a Python implementation of the factorial function:

 
def Factorial(x):
  if (x<=0) return 1
  return x*Factorial(x-1)
In the implementation above, the base case is listed as
 x <= 0
rather than
 x < 0

to return a value 1 when called with a negative number. Had the implementation been coded with <, then calling it with a negative number would lead the function never returning. This is called infinite recursion.

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.



Many beginning programmers have a real tough time understanding recursion; so if this is confusing to you, not to worry!

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!

Sample Problems

Online Resources

ACSL

The following videos show the solution to problems that have appeared in previous 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{....}$ .

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.