PyOhio Recursion Slides

An Introduction to Recursion Rinita Gulliani Twitter: @rinita1000

Why Learn About Recursion? ⦿ Software engineering technical interviews usually include questions on computer science theory ⦿ Recursion is one of the computer science theory topics that employers often test on.

What’s Different About This Talk? ⦿ Many resources are available to prepare for technical interviews, so why listen to this talk? ⦿ Many resources, while containing a wealth of valuable information, are not accessible to beginners. ⦿ I designed this talk with beginners in mind.

How “Beginner-Friendly”? ⦿ Things you need to understand to be able to understand this talk: › for loops › if statements

Agenda 1. Definition of recursion 2. Recursion in math: factorial 3. Recursion in code: factorial 4. How to Approach a Recursive Problem: Big Picture 5. Sum problem, recursively 6. Iteration (non-recursion topic) 7. Factorial and sum problems, iteratively 8. Big O Notation (non-recursion topic) 9. Interview Problem - Fibonacci 10. The pros and cons of recursion and relevant interview questions

What the Heck is Recursion? ⦿ Not just a computer science concept ⦿ In general, recursion occurs when something is defined in terms of itself or its type ⦿ In math, recursion occurs when the function on the left side is also on the right side: › ex. f(n) = f(n-1) + 7 ⦿ In computer science, recursion occurs when the function you are writing calls itself

What the Heck is Recursion? ⦿ Let’s forget about coding for a few minutes and try to understand recursion conceptually. ⦿ Let’s talk about recursion in math. ⦿ Let’s try to define factorial recursively.

Factorials ⦿ The factorial of a non-negative integer is the product of all positive integers less than or equal to that integer. ⦿ Examples: › 5! = 5 * 4 * 3 * 2 * 1 = 120 › 9! = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 362,880 › 3! = 3 * 2 * 1 = 6

How to Define Factorial Recursively? ⦿ To define factorial recursively, we need to define factorial in terms of factorial. ⦿ To put a visual to it, we’ll have an equation like this: n! = _________ ⦿ In order for the definition to recursive, there needs to be at least one factorial on the right side of the equation

How to Define Factorial Recursively? ⦿ We want a way to define the factorial in terms of another factorial so we’re going to need to look for a pattern. ⦿ Let’s see if we can identify it: › 1! = 1 › 2! = 2 * 1 › 3! = 3 * 2 * 1 › 4! = 4 * 3 * 2 * 1 › 5! = 5 * 4 * 3 * 2 * 1

How to Define Factorial Recursively? ⦿ If you could not see the pattern in the last slide, here’s a hint: › 1! = 1 › 2! = 2 * 1 › 3! = 3 * 2 * 1 › 3! = 3 * 2! ⦿ See it now?

How to Define Factorial Recursively? ⦿ I think I see a pattern, but I do not know how to write it mathematically so I will write it in words first. ⦿ It looks like the factorial of a number is that number times the factorial of the number before that number.

How to Define Factorial Recursively? ⦿ Let’s translate this to math, one step at a time: (Factorial_of_a_number) = (that_number) * (factorial_of_number_before_that_number)

How to Define Factorial Recursively? (Factorial_of_a_number) = (that_number) * (factorial_of_number_before_that_number) ⦿ Let’s call our number n. › Factorial_of_a_number : n! › That_number: n › Factorial_of_number_before_that_number: (n- 1)!

How to Define Factorial Recursively? ⦿ If we substitute our math terms into our pseudomath definition, we get this: n! = n * (n-1)! ⦿ Before we get too excited, remember that this is a possible recursive definition. ⦿ Let’s test it on a factorial to be sure that it is correct.

How to Define Factorial Recursively? ⦿ Let’s test this definition by finding 5! ⦿ Using the recursive definition: › 5! = 5 * 4! › For testing purposes, we’ll assume we know that 4! = 24. › 5! = 5 * 24 = 120 ⦿ This is correct!

How to Define Factorial Recursively? ⦿ However, this definition will not work in every case. ⦿ Recursive solutions need a base case (termination case) or you will never actually be able to solve anything. ⦿ Let’s see an example of this.

Why We Need Base Cases ⦿ Let’s try to find 7! using our recursive definition. ⦿ 7! = 7 * 6! ⦿ We need to find 6! in order to find 7! ⦿ 6! = 6 * 5! ⦿ Now, we need to find 5! in order to find 6! in order to find 7! ⦿ 5! = 5 * 4!

Why We Need Base Cases ⦿ Now we need to find 4! in order to find 5! in order to find 6! in order to find 7! ⦿ 4! = 4 * 3! ⦿ Now we need to find 3! in order to find 4! in order to find 5! in order to find 6! in order to find 7! ⦿ 3! = 3 * 2!

Why We Need Base Cases ⦿ Now we need to find 2! in order to find 3! in order to find 4! in order to find 5! in order to find 6! in order to find 7! ⦿ 2! = 2 * 1! ⦿ Now we need to find 1! in order to find 2! in order to find 3! in order to find 4! in order to find 5! in order to find 6! in order to find 7!

Why We Need Base Cases ⦿ 1! = 1 ⦿ Woah! Hold on a second! We didn’t define 1! in terms of another factorial... ⦿ Did we do something wrong? ⦿ No, because 1! = 1 is our base case.

Why We Need Base Cases ⦿ We need at least one case that is not defined recursively for every recursive solution or we will never actually solve anything. ⦿ If we write recursive code without a base case, it will run infinitely (until it crashes)

Why We Need Base Cases ⦿ Notice that we have not actually solved 7!, 6!, 5!, 4!, 3!, or 2! yet. ⦿ Now that we know our base case (1! = 1), we can work our way backwards to solve 7!

Why We Need Base Cases ⦿ Now that we know 1!, we can find 2! ⦿ 2! = 2 * 1! = 2 * 1 = 2 ⦿ And now that we know 2!, we can find 3! ⦿ 3! = 3 * 2! = 3 * 2 = 6 ⦿ And now that we know 3!, we can find 4! ⦿ 4! = 4 * 3! = 4 * 6 = 24

Why We Need Base Cases ⦿ And now that we know 4!, we can find 5! ⦿ 5! = 5 * 4! = 5 * 24 = 120 ⦿ And now that we know 5!, we can find 6! ⦿ 6! = 6 * 5! = 6 * 120 = 720 ⦿ Finally, we can find 7! ⦿ 7! = 7 * 6! = 7 * 720 = 5040

Why We Need Base Cases ⦿ Hopefully, this example illustrated why we need a base case and what the base case does. ⦿ Note that we also could have defined our base case as 0! = 1.

Recursive Definition of Factorial ⦿ Earlier, we defined n! like this: n! = n * (n-1)! ⦿ Let’s add our base case to give a complete definition: 1 n=1, n! = n * (n-1)! n>1

Parts of a Recursive Definition ⦿ Every recursive solution needs at least one base case and at least one recursive case. ⦿ A recursive solution can have more than one base case and/or more than one recursive case.

Review of What We’ve Learned So Far ⦿ Recursion occurs when something is defined in terms of itself or its type ⦿ In computer science, this happens when a function calls itself ⦿ Recursive solutions have 2 parts*: 1) Base case: For factorial, this is 1! = 1 2) Recursive case: For factorial, this is n! = n * (n-1)! *a recursive solution can have multiple base cases and/or multiple recursive cases

Now, Let’s Code! ⦿ Since we’ve just discussed factorial conceptually, let’s code it! ⦿ More specifically, let’s write a recursive function called factorial that takes in an integer, n, and returns the factorial of that number.

Let’s Write Pseudocode! ⦿ Problem: Let’s write a recursive function called factorial that takes in an integer, n, and returns the factorial of that number. ⦿ Maybe some of you are intimidated by this problem. ⦿ Let’s write pseudocode. ⦿ Let’s talk about what we know and take it one step at a time.

⦿ Problem: Write a recursive function called factorial that takes in an integer, n, and returns the factorial of that number. ⦿ Something we know: The function will be called factorial.

⦿ Problem: Write a recursive function called factorial that takes in an integer, n, and returns the factorial of that number. ⦿ Something we know: The function will take in a variable, n.

⦿ Problem: Write a recursive function called factorial that takes in an integer, n, and returns the factorial of that number. ⦿ Something we know: The function will return the factorial of n. Let’s call this result

⦿ Problem: Write a recursive function called factorial that takes in an integer, n, and returns the factorial of that number. ⦿ Something we know: Every recursive solution will have a base case and a recursive case.

⦿ Problem: Write a recursive function called factorial that takes in an integer, n, and returns the factorial of that number. ⦿ Something we know: The base case is 1! = 1. Let’s translate this to code.

⦿ Problem: Write a recursive function called factorial that takes in an integer, n, and returns the factorial of that number. ⦿ Something we know: Our recursive definition for factorial is n! = n * (n-1)! ⦿ Tricky to code; let’s add that line as is (since this is pseudocode)

Let’s Write Pseudocode! ⦿ We’ve defined the function, passed in parameters, returned the result, and defined the base case and the recursive case so our pseudocode is complete! ⦿ We only have one line in our pseudocode that isn’t valid code so let’s translate it.

Let’s Code ⦿ n! = n * (n-1)! ⦿ result = n * factorial(n-1) ⦿ Let’s add this line of code to our function!

How To Approach a Recursive Problem - Big Picture 1. Finding the pattern (recursive case) a. Identify a possible pattern. b. Define it in words. c. Turn those words into pseudomath. d. Turn that pseudomath into real math. e. Test the pattern to make sure it is correct. f. If so, this is the recursive case (or cases).

How to Approach a Recursive Problem - Big Picture 2. Find the base cases: ⦿ Sometimes the problem implies them ⦿ Case(s) that cannot be defined recursively

How to Approach a Recursive Problem - Big Picture 3. Pseudocode - Take it one step at a time. a. Declare the function. b. Pass in parameters. c. Write a return statement. d. Put comments in the body of the function to be placeholders for the base case(s) and the recursive case(s). e. Attempt to write code for each case. If a case is tricky, write pseudocode.

How to Approach a Recursive Problem - Big Picture 4. Translate pseudocode to code: Translate any statements that are not valid code in your pseudocode.

Sum Problem: Calculate Sum From 1 to n ⦿ We are awesome! ⦿ Let’s do another problem! ⦿ Write a function that takes in an integer, n, and calculates the sum of all integers from 1 to n. ⦿ Let’s write this function recursively using the steps we talked about.

Sum From 1 to n ⦿ Step 1: Find the recursive case. ⦿ Since we first derive a mathematical definition, let’s refer to our sum as f(n). ⦿ If n = 2, f(2) = 1 + 2 ⦿ If n = 3, f(3) = 1 + 2 + 3 ⦿ If n = 4, f(4) = 1 + 2 + 3 + 4 ⦿ Step 1a is to identify a possible pattern

Sum From 1 to n ⦿ Here’s a hint: ⦿ If n = 3, f(n) = 1 + 2 + 3 ⦿ If n = 4, f(n) = 1 + 2 + 3 + 4

Sum From 1 to n ⦿ I think I see a possible pattern. ⦿ Step 1b is to write the pattern in words. ⦿ It looks like, f(n) equals n plus the solution for the number before n.

Sum From 1 to n ⦿ Step 1c is to turn the words into pseudomath. ⦿ f(n) = n + answer_for_number_before_n

Sum From to 1 to n ⦿ f(n) = n + answer_for_number_before_n ⦿ Step 1d is to turn this definition into actual math. ⦿ Only the term, answer_for_number_before_n is not valid math and this term is represented by f(n-1). ⦿ Thus, we have this statement: f(n) = n + f(n-1)

Sum From 1 to n ⦿ Step 1e is to confirm that this definition is correct. ⦿ Let’s find f(6). ⦿ f(6) = 6 + f(5). ⦿ For testing purposes, we’ll assume we know f (5) is 15. ⦿ f(6) = 6 + 15 = 21 ⦿ This is correct so this is our recursive case.

Sum From 1 to n ⦿ Step 2 is to find the base cases. ⦿ Our base case is n=1 because our sum goes from 1 to n so for n=1, there would be nothing to add to 1. 1, if n=1 f(n) = n + f(n-1), if n>1

Sum From 1 to n ⦿ Step 3 is to write pseudocode. ⦿ Remember: Take it one step at a time.

Problem: Write a function that takes in an integer, n, and calculates the sum of all integers from 1 to n. Step 3a is to declare the function. Note: We did not name the function sum because Python has a built- in function named sum.

Problem: Write a function, sum, that takes in an integer, n, and calculates the sum of all integers from 1 to n. Step 3b is to pass in parameters.

Problem: Write a function, sum, that takes in an integer, n, and calculates the sum of all integers from 1 to n. Step 3c is to write a return statement. Let’s call this value result.

Problem: Write a function, sum, that takes in an integer, n, and calculates the sum of all integers from 1 to n. Step 3d is to add comments to serve as placeholders for the base case(s) and the recursive case(s).

Problem: Write a function, sum, that takes in an integer, n, and calculates the sum of all integers from 1 to n. Step 3e is to attempt to write code for each of these cases. The base case is easy, but the recursive case is a bit tricky. Since this is only pseudocode, I’ll put the mathematical definition as a placeholder.

Problem: Write a function, sum, that takes in an integer, n, and calculates the sum of all integers from 1 to n. Step 4 is to translate any lines that aren’t valid code. We only need to translate one line. ⦿ f(n) = n + f(n-1) ⦿ result = n + sum(n-1)

Sum From 1 to n: Recursive Solution

We Did It! ⦿ Wow, we are awesome! ⦿ We just wrote 2 recursive functions (one for factorial and one for our sum problem). ⦿ Let’s take a step back and talk about technical interviews. ⦿ In a real interview, you may be asked to solve a certain problem both recursively and iteratively.

Iteration ⦿ Iteration is NOT recursion; they are two different techniques ⦿ Iteration uses loops ⦿ Remember the difference like this: › Recursion – function calls itself › Iteration – uses loops (for loop, while loop, etc.)

Factorial, Iteratively ⦿ Now that we have a basic idea of how recursion and iteration are different, let’s take a quick peek at an iterative solution to our factorial problem.

Factorial: Recursive and Iterative Solutions

Sum From 1 to n: Iterative Solution

Sum From 1 to n: Recursive and Iterative Solutions

Big O Notation: A Very Brief Introduction ⦿ Many ways to write functions that do the same thing (for example, recursively or iteratively), so how do we decide which way is best? ⦿ Faster code is usually better so it is useful if we have a way to measure the runtime of a function.

Big O Notation: A Very Brief Introduction ⦿ Computer programmers usually do not measure the runtime of function in a unit of time like seconds or minutes. ⦿ Why not? ⦿ Well, many factors about the hardware and software on computer can affect its runtime.

Big O Notation: A Very Brief Introduction ⦿ Thus, the same code could have different runtimes even on the same computer so this measurement is not very useful to computer scientists. ⦿ Instead, computer scientists measure how runtime grows as the size of the input increases. ⦿ They do this using a form of asymptotic notation called Big O notation.

Big O Notation: A Very Brief Introduction Here are a few basic rules about Big O Notation: 1. Unless otherwise stated, Big O notation refers to the worst-case. Worst case means the kind of input that would lead to the longest runtime.

Big O Notation: A Very Brief Introduction Basic Rules for Big O Notation: 2. Here are a few examples of how to write Big O Notation: ⦿ O(n) ⦿ O(log n) It’s a capital O followed by parentheses. In the parentheses is a mathematical expression that represents the runtime.

Big O Notation: A Very Brief Introduction Basic Rules for Big O Notation: 3. How to read Big O notation: ⦿ O(n): “order of n” or “Big O of n” ⦿ O(log n): “order of log n” or “Big O of log n”

Big O Notation: A Very Brief Introduction Basic rules for Big O Notation: 4. Drop constant terms. ⦿ Example: If a function’s runtime grows at a rate of 2n as n increases, the constant is dropped and it is considered to be O(n). ⦿ There is no such thing as O(2n) in proper Big O notation.

Big O Notation: A Very Brief Introduction Basic Rules for Big O Notation: 5. Only keep the highest-order term. ⦿ Example: If a function’s runtime grows at a rate of n2 + n + log n, it is O(n2 ). ⦿ Example 2: If a function’s runtime grows at a rate of 7n2 + 4n + log n, it is also O(n2 ).

Big O Notation: A Conceptual Example ⦿ Let’s forget about code for a minute and try to imagine a conceptual example of Big O notation. ⦿ Imagine that we have a bookshelf with n books that are not in any particular order. ⦿ We want to purchase a copy of the latest Harry Potter book, but only if we do not already have one.

Big O Notation: A Conceptual Example ⦿ How long will it take us to search the bookshelf for the book in Big O notation? ⦿ Remember to assume the worst-case: The worst case is if the book is not on the shelf. ⦿ In this case, it would take n units of time. ⦿ O(n)

Big O Notation: A Very Brief Introduction ⦿ This is a very brief introduction to Big O notation. ⦿ I do not expect you to be able to calculate Big O notation for a function based on listening to this talk alone.

Recursion vs Iteration: Which is Better? ⦿ Some of you may be wondering which technique is better: recursion or iteration? ⦿ Guess what? ⦿ I’m not going to tell you yet. ⦿ Actually, I only made this slide so that you’d start wondering which technique is better.

Fibonacci Sequence ⦿ Let’s try another problem: the Fibonacci sequence. ⦿ Specifically, write a function fib() that takes an integer n and returns the nth Fibonacci number. ⦿ This is a real interview question.

Fibonacci Sequence ⦿ When we did the factorial problem, we derived the mathematical definition ourselves. ⦿ However, I’m going to give you the definition. 0 if n = 0 f(n) = 1 if n = 1 f(n-1) + f(n-2) if n > 1

Fibonacci Sequence ⦿ We seem to have 3 parts to this definition, unlike the 2 parts we had with our factorial definition and our sum definition. ⦿ Recall that we had discussed that there can be more than one base case and more than one recursive case. ⦿ In this problem, we have two base cases

Fibonacci Sequence ⦿ Let’s first come up with a recursive solution. ⦿ Since we already have a mathematical recursive definition (recurrence relation), we can skip steps 1 and 2 of our process. ⦿ Let’s start with step 3 and write some pseudocode.

Problem: Write a function, fib(), that takes in an integer, n, and returns the nth number of the Fibonacci sequence. Step 3a: Declare the function.

Problem: Write a function, fib(), that takes in an integer, n, and returns the nth number of the Fibonacci sequence. Step 3b: Pass in parameters.

Problem: Write a function, fib(), that takes in an integer, n, and returns the nth number of the Fibonacci sequence. Step 3c is to write the return statement. Let’s call the value we’re returning result.

Problem: Write a function, fib(), that takes in an integer, n, and returns the nth number of the Fibonacci sequence. Step 3d is to place comments in the body of the function to be placeholders for the base case(s) and the recursive case(s). We have 2 base cases and 1 recursive case.

Problem: Write a function, fib(), that takes in an integer, n, and returns the nth number of the Fibonacci sequence. Step 3e is to attempt to write code for each case. The base cases are easy to write, but the recursive case is a bit trickier.

Problem: Write a function, fib(), that takes in an integer, n, and returns the nth number of the Fibonacci sequence. Step 4 is to translate any lines in your pseudocode that are not valid code. We only have one line like this: ⦿ f(n) = f(n-1) + f(n-2) ⦿ result = fib(n-1) + fib(n-2)

Recursion vs Iteration ⦿ Earlier, we started to wonder whether recursion or iteration is a better technique. ⦿ The answer: It depends.

Recursion: The Positives ⦿ If you prepare for technical interviews, you will come across other data structures and algorithms that are implemented nicely with recursion. ⦿ In general, recursive solutions look more “elegant” than iterative solutions.

The Dark Side of Recursion ⦿ Even when Big O runtimes for the iterative and the recursive solutions are the same, the recursive solution will be slower because all those function calls must be stored in the stack

The Darker Side of Recursion: Fibonacci ⦿ Let’s ignore the issue of calls to the stack and just talk about the runtime of the recursive Fibonacci solution. ⦿ The time complexity of the recursive solution is O(2n ). ⦿ O(2n ) = VERY BAD! ⦿ To understand why this solution is O(2n ), let’s look at a recursion tree.

fib(4) fib(3) fib(2) fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) RecursionTreeforRecursive SolutionofFibonacci

Fibonacci Problem Follow-Up Interview Questions ⦿ Question: Which solution to the Fibonacci problem is faster? ⦿ Answer: The iterative solution. It has a runtime of O(n)* which is far better than the runtime of the recursive solution, O(2n ). *Note: Some computer scientists consider the Big O runtime of the iterative solution to be O(n2 ). Either way, the solution is still far superior to the recursive solution.

Fibonacci Problem Follow-Up Interview Questions ⦿ Question: Assuming that Big O runtime is the same, which is faster, recursion or iteration? ⦿ Answer: Usually iteration. Recursion requires repeated calls to the stack which slows the runtime down.

⦿ Questions? ⦿ Twitter: @rinita1000

PyOhio Recursion Slides

More Related Content

Similar to PyOhio Recursion Slides

Recently uploaded

PyOhio Recursion Slides