In mathematics and computer science, recursion is a function or procedure that is defined in terms of itself.
A classic example of a recursive algorithm is the calculation of the Fibonacci Sequence, a mathematical formula known to mathematicians since at least the 4th century B.C in India.
A classic example of a recursive algorithm is the calculation of the Fibonacci Sequence, a mathematical formula known to mathematicians since at least the 4th century B.C in India.
0
and 1
.A classic example of a recursive algorithm is the calculation of the Fibonacci Sequence, a mathematical formula known to mathematicians since at least the 4th century B.C in India.
The first two numbers in the sequence are 0
and 1
.
Every subsequent number in the sequence is the sum of the previous two.
A classic example of a recursive algorithm is the calculation of the Fibonacci Sequence, a mathematical formula known to mathematicians since at least the 4th century B.C in India.
The first two numbers in the sequence are 0
and 1
.
Every subsequent number in the sequence is the sum of the previous two.
e.g. 0
, 1
, 1
, 2
, 3
, 5
, 8
, 13
, 21
, 34
, 55
, etc.
A classic example of a recursive algorithm is the calculation of the Fibonacci Sequence, a mathematical formula known to mathematicians since at least the 4th century B.C in India.
The first two numbers in the sequence are 0
and 1
.
Every subsequent number in the sequence is the sum of the previous two.
e.g. 0
, 1
, 1
, 2
, 3
, 5
, 8
, 13
, 21
, 34
, 55
, etc.
this is a recursive algorithm because to find the nth number in the sequence, you must determine the n-1 and n-2 numbers in the sequence.
A classic example of a recursive algorithm is the calculation of the Fibonacci Sequence, a mathematical formula known to mathematicians since at least the 4th century B.C in India.
The first two numbers in the sequence are 0
and 1
.
Every subsequent number in the sequence is the sum of the previous two.
e.g. 0
, 1
, 1
, 2
, 3
, 5
, 8
, 13
, 21
, 34
, 55
, etc.
this is a recursive algorithm because to find the nth number in the sequence, you must determine the n-1 and n-2 numbers in the sequence.
mathematically, this formula could be: F(n) = F(n − 1) + F(n − 2)
In Java, a recursive formula could be written to calculate the Fibonacci number at any nth position in the sequence.
In Java, a recursive formula could be written to calculate the Fibonacci number at any nth position in the sequence.
public static int fibonacci(int n) { if (n == 1) return 0; if (n == 2) return 1; return fibonacci(n - 1) + fibonacci(n - 2);}
The following diagram illustrates the changes to the call stack over time as our algorithm calculates the Fibonacci number at position 5
in the sequence.
The following diagram illustrates the changes to the call stack over time as our algorithm calculates the Fibonacci number at position 5
in the sequence.
The following diagram illustrates the changes to the call stack over time as our algorithm calculates the Fibonacci number at position 5
in the sequence.
Notice that the fibonacci()
method is called 9 times: once from main()
and 8 additional recursive calls.
Let's take a simpler example of a recursive algorithm for a function used to flip a string backwards.
Let's take a simpler example of a recursive algorithm for a function used to flip a string backwards.
"e"
backwards is "e"
. So simply return the original.Let's take a simpler example of a recursive algorithm for a function used to flip a string backwards.
If the original string is only one character long, the reversed form is the same as the original. For example, "e"
backwards is "e"
. So simply return the original.
Otherwise, return the last character of the original string concatenated to the reversed version of the remainder (excluding the last character). For example, "nonplussed"
backwards is "d" + backwards("nonplusse")
In Java, the recursive string flipping algorithm might look like this:
In Java, the recursive string flipping algorithm might look like this:
public static String backwards(String original) { // if string is one character or less, return the original if (original.length() <= 1) { return original; } // otherwise, return the last character + the backwards of the remainder char lastChar = original.charAt(original.length() - 1); String remainder = original.substring(0, original.length() - 1); return lastChar + backwards(remainder);}
Understanding recursion can sometimes be assisted by diagramming the step-wise changes to the function call stack, including the arguments and return values from each new function invocation.
Another illustrative example is to solve power equations recursively. For example, the problem of calculating the value of a base raised to a certain exponent, such as 612.
Another illustrative example is to solve power equations recursively. For example, the problem of calculating the value of a base raised to a certain exponent, such as 612.
0
, we can simply return 1
, since anything raised to the power 0
equals 1
.Another illustrative example is to solve power equations recursively. For example, the problem of calculating the value of a base raised to a certain exponent, such as 612.
If the desired power is 0
, we can simply return 1
, since anything raised to the power 0
equals 1
.
Otherwise, we can decompose the problem and return base x basepow - 1. For example, 612 is the same as 6 x 611
In Java, the recursive power algorithm might look like this:
In Java, the recursive power algorithm might look like this:
public static int power(int base, int exp) { if (exp == 0) { return 1; } return base * power(base, exp-1);}
The changes to the function call stack over time for calculating 52 might look like:
A recursive function almost universally follows a general pattern.
A recursive function almost universally follows a general pattern.
A recursive function almost universally follows a general pattern.
check for a base case, and return a fixed value that doesn't require recursion, if found
otherwise, decompose the problem in some way and return a value obtained from a recursive function call
For example, let's revisit the Fibonacci algorithm.
For example, let's revisit the Fibonacci algorithm.
public static int fibonacci(int n) { // base case: we know the answer if (n == 1) return 0; if (n == 2) return 1; // recursive case: return the sum of two recursive calls return fibonacci(n - 1) + fibonacci(n - 2);}
For example, let's revisit the Fibonacci algorithm.
public static int fibonacci(int n) { // base case: we know the answer if (n == 1) return 0; if (n == 2) return 1; // recursive case: return the sum of two recursive calls return fibonacci(n - 1) + fibonacci(n - 2);}
1
or 2
- we simply return a 0
or 1
in response.For example, let's revisit the Fibonacci algorithm.
public static int fibonacci(int n) { // base case: we know the answer if (n == 1) return 0; if (n == 2) return 1; // recursive case: return the sum of two recursive calls return fibonacci(n - 1) + fibonacci(n - 2);}
the base case occurs when the argument is either 1
or 2
- we simply return a 0
or 1
in response.
in the recursive case, we return the sum of two recursive calls with smaller arguments than the original.
And let's revisit the backwards string algorithm.
And let's revisit the backwards string algorithm.
public static String backwards(String original) { // base case: return the original if (original.length() <= 1) { return original; } // recursive case: return the last character + the backwards of the remainder char lastChar = original.charAt(original.length() - 1); String remainder = original.substring(0, original.length() - 1); return lastChar + backwards(remainder);}
And let's revisit the backwards string algorithm.
public static String backwards(String original) { // base case: return the original if (original.length() <= 1) { return original; } // recursive case: return the last character + the backwards of the remainder char lastChar = original.charAt(original.length() - 1); String remainder = original.substring(0, original.length() - 1); return lastChar + backwards(remainder);}
And let's revisit the backwards string algorithm.
public static String backwards(String original) { // base case: return the original if (original.length() <= 1) { return original; } // recursive case: return the last character + the backwards of the remainder char lastChar = original.charAt(original.length() - 1); String remainder = original.substring(0, original.length() - 1); return lastChar + backwards(remainder);}
the base case occurs when the length is 1 or 0, we return the original.
the recursive case decomposes the problem and returns a value resulting, in part, from recursion.
The same pattern applies to the power equation.
The same pattern applies to the power equation.
public static int power(int base, int exp) { // base case: return 1 when raised to power 0 if (exp == 0) { return 1; } // recursive case: decompose the problem including recursion return base * power(base, exp-1);}
The same pattern applies to the power equation.
public static int power(int base, int exp) { // base case: return 1 when raised to power 0 if (exp == 0) { return 1; } // recursive case: decompose the problem including recursion return base * power(base, exp-1);}
0
... we return 1
.The same pattern applies to the power equation.
public static int power(int base, int exp) { // base case: return 1 when raised to power 0 if (exp == 0) { return 1; } // recursive case: decompose the problem including recursion return base * power(base, exp-1);}
the base case occurs when the exponent is 0
... we return 1
.
the recursive case decomposes the problem and returns a value resulting, in part, from a recursive call.
Fractals are a category of algorithmically-generated images that exhibit a high-degree of self-similarity.
Fractals are a category of algorithmically-generated images that exhibit a high-degree of self-similarity.
Fractals are a category of algorithmically-generated images that exhibit a high-degree of self-similarity.
In other words, the whole image can be decomposed into parts that resemble, or are identical, to the whole image.
They are typically generated using recursive algorithms.
Fractals are a category of algorithmically-generated images that exhibit a high-degree of self-similarity.
In other words, the whole image can be decomposed into parts that resemble, or are identical, to the whole image.
They are typically generated using recursive algorithms.
we will not try to derive the algorithms used to generate fractals, but will simply enjoy some pretty recursive pictures.
One of the "classic" fractal images is the Sierpiński triangle.
Perhaps the most famous fractal images are those derived from the Mandelbrot set.
Perhaps the most famous fractal images are those derived from the Mandelbrot set.
Recursion takes some time to get familiar with. However, it can describe some problems that are inherently recursive in a more intuitive way, with simpler code, than other forms of iteration.
Keyboard shortcuts
↑, ←, Pg Up, k | Go to previous slide |
↓, →, Pg Dn, Space, j | Go to next slide |
Home | Go to first slide |
End | Go to last slide |
Number + Return | Go to specific slide |
b / m / f | Toggle blackout / mirrored / fullscreen mode |
c | Clone slideshow |
p | Toggle presenter mode |
t | Restart the presentation timer |
?, h | Toggle this help |
Esc | Back to slideshow |