# Difference between revisions of "Recursive Functions"

Marc Brown (Talk | contribs) |
Marc Brown (Talk | contribs) |
||

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 | + | 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 | + | 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$}$$ | ||

− | + | Here is a Python implementation of the Fibonacci function: | |

− | + | ||

− | + | ||

::<syntaxhighlight lang="python"> | ::<syntaxhighlight lang="python"> | ||

− | def Fibonacci( | + | 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! | + | (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$}$$ | ||

− | + | 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( | + | 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> | ||

− | + | 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''. | ||

− | + | === 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! | 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.

## Contents

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

```
x <= 0
```

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