nyu-daniel-zint / intro-to-computer-science-2024-spring / recursion
+ - 0:00:00
Notes for current slide
Notes for next slide

Recursion

1 / 21

Overview

3 / 21

Overview

Concept

In mathematics and computer science, recursion is a function or procedure that is defined in terms of itself.

3 / 21

Fibonacci Numbers

4 / 21

Fibonacci Numbers

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

4 / 21

Fibonacci Numbers

A 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.
4 / 21

Fibonacci Numbers

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

4 / 21

Fibonacci Numbers

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

4 / 21

Fibonacci Numbers

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

4 / 21

Fibonacci Numbers

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

4 / 21

Fibonacci Numbers

In code

In Java, a recursive formula could be written to calculate the Fibonacci number at any nth position in the sequence.

5 / 21

Fibonacci Numbers

In code

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);
}
5 / 21

Fibonacci Numbers

Call stack

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.

6 / 21

Fibonacci Numbers

Call stack

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.

Calculating Fibonacci numbers

6 / 21

Fibonacci Numbers

Call stack

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.

Calculating Fibonacci numbers

  • Click to view larger

  • Notice that the fibonacci() method is called 9 times: once from main() and 8 additional recursive calls.

6 / 21

Flipping Strings Backwards

7 / 21

Flipping Strings Backwards

Another example

Let's take a simpler example of a recursive algorithm for a function used to flip a string backwards.

7 / 21

Flipping Strings Backwards

Another example

Let's take a simpler example of a recursive algorithm for a function used to flip a string backwards.

  1. 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.
7 / 21

Flipping Strings Backwards

Another example

Let's take a simpler example of a recursive algorithm for a function used to flip a string backwards.

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

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

7 / 21

Flipping Strings Backwards

In code

In Java, the recursive string flipping algorithm might look like this:

8 / 21

Flipping Strings Backwards

In code

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);
}
8 / 21

Flipping Strings Backwards

Call stack

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.

9 / 21

Flipping Strings Backwards

Call stack

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.

Flipping a string backwards

9 / 21

Calculating Powers

10 / 21

Calculating Powers

Solving power equations

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.

10 / 21

Calculating Powers

Solving power equations

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.
10 / 21

Calculating Powers

Solving power equations

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

10 / 21

Calculating Powers

In code

In Java, the recursive power algorithm might look like this:

11 / 21

Calculating Powers

In code

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);
}
11 / 21

Calculating Powers

Call stack

The changes to the function call stack over time for calculating 52 might look like:

12 / 21

Calculating Powers

Call stack

The changes to the function call stack over time for calculating 52 might look like:

Calculating powers

12 / 21

Generalized Pattern

13 / 21

Generalized Pattern

Concept

A recursive function almost universally follows a general pattern.

13 / 21

Generalized Pattern

Concept

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
13 / 21

Generalized Pattern

Concept

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

13 / 21

Generalized Pattern

Fibonacci example

For example, let's revisit the Fibonacci algorithm.

14 / 21

Generalized Pattern

Fibonacci example

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);
}
14 / 21

Generalized Pattern

Fibonacci example

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.
14 / 21

Generalized Pattern

Fibonacci example

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.

14 / 21

Generalized Pattern

Flipping string backwards example

And let's revisit the backwards string algorithm.

15 / 21

Generalized Pattern

Flipping string backwards example

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);
}
15 / 21

Generalized Pattern

Flipping string backwards example

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.
15 / 21

Generalized Pattern

Flipping string backwards example

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.

15 / 21

Generalized Pattern

Calculating powers

The same pattern applies to the power equation.

16 / 21

Generalized Pattern

Calculating powers

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);
}
16 / 21

Generalized Pattern

Calculating powers

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.
16 / 21

Generalized Pattern

Calculating powers

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.

16 / 21

Fractals

17 / 21

Fractals

Concept

Fractals are a category of algorithmically-generated images that exhibit a high-degree of self-similarity.

17 / 21

Fractals

Concept

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.
17 / 21

Fractals

Concept

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.

17 / 21

Fractals

Concept

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.

17 / 21

Fractals

Sierpiński triangle

One of the "classic" fractal images is the Sierpiński triangle.

18 / 21

Fractals

Sierpiński triangle

One of the "classic" fractal images is the Sierpiński triangle.

Sierpiński triangle

18 / 21

Fractals

Koch snowflake

Another is the Koch snowflake.

19 / 21

Fractals

Koch snowflake

Another is the Koch snowflake.

Koch snowflake

19 / 21

Fractals

Mandelbrot set

Perhaps the most famous fractal images are those derived from the Mandelbrot set.

20 / 21

Fractals

Mandelbrot set

Perhaps the most famous fractal images are those derived from the Mandelbrot set.

Mandelbrot set fractal

20 / 21

Conclusions

21 / 21

Conclusions

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.

21 / 21
Paused

Help

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