Lecture 1



CSC 401 NotesRecursion: IntroductionRecursionA recursive method is a method that solves a problem by having a function call itself! Naturally, this may seem like a recipe for an infinite loop of sorts. However, we will see that we build into our problem a “base case” where we do not tell the function to call itself. At that point and we can "trace" our way back to the starting point. I realize this sounds confusing, but not to worry! We will discuss here with examples, and, of course, you have your book for further and more detailed reading as needed.Why recursion?Recursion turns out to be a particularly helpful tool for certain programming problems. We can't always tell what they are at the outset. But when we learn to "think recursively", we start spotting situations where a recursive solution might apply and be effective.There are many situations where a problem that seems tricky to solve, turns out to have a much more intuitive solution using recursion. Some programming languages are primarily recursive in nature (e.g. Lisp and Scheme), where loops are almost completely absent from programs.Any recursive method consists of:One or more base cases: these are the portions of the problem for which an immediate solution (e.g. the return value) is known. One or more recursive calls: Again, a "recursive call" means that the function calls itself. However, in order to avoid infinite recursion each successive recursive call must be in some way “smaller” than the original problemThe best way to learn recursion is to practice, a lot. For this reason, we will see many examples during this part of the course. Note: Many of the examples that we will look at do not necessarily require recursion. However, we will use them to explain how recursion works. Printing numbersLet’s start with a relatively trivial example. Consider the problem of printing the numbers from n down to 1 for some (positive) value of n.Input: A positive integer nOutput: The numbers from n down to 1, printed one per lineSample runs:>>> countdown(10)10987654321Blast off!>>> countdown(1)1Blast off!>>> countdown(0)#n = 0Blast off!While we could, of course, do this very easily using a loop, let’s see if we can come up with a recursive algorithm to solve the problem.“Thinking Recursively” Thinking recursively means asking ourselves whether there is a recursive solution to a programming problem. To do so, we need to: Determine if we can construct subproblems that when solved and combined, produce the solution to the original problem. Come up with one or more “base cases”Using our count-down problem, let’s first think about the base case. At what point can we definitively provide an answer (e.g. a return value)?One possible answer: If we have no numbers to print, we could just print the “Blast off!” message.How can we use this information to find a recursive solution?We could print the first number we are required to print.Then we could make a recursive call to print any remaining numbers.And of course, we must not forget the “Blast off!” message at the end.def countdown(n): 'count from n down to 1' if n == 0: #the 'base case' print('Blast off!') else: print(n) countdown(n-1) #the function calls itself!Invoke this function with a few different (positive) values for n. Also try n=0. Thought Question: If you invoke the function with a negative value for n what would happen? (Enlarge the font to see the solution). Answer: Infinite loop.Problem: Can you modify the code so that if some one invokes using a negative number, it doesn’t have an infinite loop, and instead, simply prints ‘Blast Off!’?Answer: Modify the base case to say: if n<=0Printing verticallyConsider the problem of printing an the digits of an integer number vertically:Input: A non-negative integer number nOutput: The integer n, with each of its digits stacked verticallyExample: If the input is 5729, the output is:5729We will write a recursive algorithm to solve the problem.This is a situation that turns out to be easily solvable if you remember to give a shot at “thinking recursively”. Recall that thinking recursively, means we need to 1) construct subproblems that when solved and combined can produce the solution to the original problem, and 2) be able to come up with 1 or more base cases. (Yes, sometimes there are a few different possible base cases). NOTE: When you are new to recursion, our algorithm might not seem remotely obvious or intuitive. But, as we’ve discussed, with more experience, you will get better at spotting problems that may have recursive solutions. I.e. You will get better at ‘thinking recursively’. So don’t get discouraged or psyched out!With that said, let’s look at a recursive solution to this problem:Let’s first think about the base case. When would the problem be easy?If we had just one digit to print, then we would print it on a line by itself and would be done.How can we use that to find a recursive solution?We could print all but the last digit by making a recursive call. (Why the last digit and not the first one?)Then we could print the last digit. (Why not print the last digit before the recursive call?)Here is the code that will solve the problem using recursion:def vertical(n): if n < 10: print(n) #this is the base case else: vertical(n // 10) # Recursive function call print(n % 10) Note the recursive function call on line #5 of the function. Recall:// does integer division e.g. 10//3 = 3% is the modulus operator e.g. 10%3 = 1Let’s study this solution with an example. What happens when we call vertical on input n=361?EXAMPLE: Invoking the function vertical(361): Since 361 is not less than 10, the call to vertical(36) is made.Before this call gets executed the computer must store all the information necessary to complete the original call vertical(361) after vertical(36) is completed.This “necessary information” includes:the values of all variables in the current iteration of the function where execution should resume once the recursive function call terminates This information is stored in a construct we call the activation record.This activation record is placed on a famous programming construct called the stack. So before executing vertical(36), we create the activation record:Function to return to: vertical()Parameters: Just one: n=361Return to: end of line 5and we place this activation record on the stack. We then invoke the following function:vertical(36) Since 36 is not less than 10, the call to vertical(3) is made.Before executing vertical(3) we must store the activation record of the current process:Function "vertical", n=36, Return to: end of line 5We then invoke the following function: vertical(3)Since 3 is less than 10, we output 3 and return … where?Back to end of line #5 in the execution of vertical(36)We then invoke the following function: vertical(36)We output 6 and return to end of line 5 of the execution of vertical(361)We then invoke the following function:vertical(361)We output 1 and the function ends. Because there are no items remaining on the stack, the application ends.ExercisesSolutions to all of these can be found in: recursion_exercises.py Problem 1: Write a recursive function called revVert(n) that ouputs the digits in the number n, but in reversed order. Input: A non-negative integer nOutput: The integer n, with its digits stacked vertically, in reverse order.Example: If n = 361, then the program should output:163How can we modify the recursive solution we came up with in vertical(n) to get the solution to this problem?Problem 2: Write a recursive function printLst() that takes a list as a parameter and prints the items in the list, one per line. Hint: The idea here is that with a single item in the list, just print that item. If there is more than one item, invoke the printLst() function with the remainder of the list (aside from the single item). >>> printLst([1, 2, 3])123>>> printLst([1])1Problem 3: Write a recursive function cheer() that on an integer parameter n, will output n-1 strings “Hip” followed by “Hurray”.>>> cheer(5)HipHipHipHipHurray>>> cheer(3)HipHipHurray>>> cheer(1)Hurray>>> cheer(2)HipHurray>>> cheer(0)HurrayExercisesAll of the solutions can be found in the file recursion_exercises.py.Problem: Write a recursive function pattern() that prints a number pattern as shown below:>>> pattern(1)1 >>> pattern(2)1 2 1 >>> pattern(3)1 2 1 3 1 2 1 >>> pattern(4)1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 >>> pattern(5)1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1If you are having trouble spotting the pattern, the idea is that, for example, pattern(4) will print the results of pattern(3) followed by a '4' followed by pattern(3) again. pattern() problem redux: Write a recursive function makePattern() that returns a string consisting of the same numbers as are printed in pattern().>>> s = makePattern(1)>>> s'1'>>> s = makePattern(2)>>> s'1 2 1'>>> s = makePattern(3)>>> s'1 2 1 3 1 2 1'>>> s = makePattern(4)>>> s'1 2 1 3 1 2 1 4 1 2 1 3 1 2 1'The factorial functionFor a given non-negative integer n, n! (read “n factorial”) is defined as the product of all the positive integers up to n: n (n-1) (n-2) (n-3) … 1.It’s easy to write a loop that solves this. What about a recursive definition? How can we write n! in terms of a smaller factorial?Exercise: Find a recursive definition and write it in Python.How many calls to factorial are made for a parameter n?One for nOne for n-1One for n-2…One for 1 A total of n callsThe exponent functiona to the power n is just a * a * a *… * a, i.e. a multiplied by itself n times.This can be easily implemented iteratively using a loop:def loop(a, n):ans = 1for i in range(n):ans = ans * areturn ansHow many multiplications are done?Using recursion and the addition rule for exponents we can reduce the number of multiplications.What is the addition rule for exponents?a2n = an * an = an+na2n+1 = an * an * a = an + n + 1See the solution in exponent.py.How many multiplications are done? How does it compare with the iterative definition?List printing, reduxWhat if we want to print a list that contains sublists? How can we modify the solution we developed to work in that case?We need to add several bases cases to handle various cases for the first element.What values can the first element be? Which of those values is relevant for making recursive calls?Exercise: Modify the solution produced previously to work on multi-dimensional lists. It should work as follows:>>> listPrint([1, 2, 3, 4])1234>>> listPrint([[[1, [2], [3], [[[4]]]], [5], [[6, 7], 8]], 9])123456789>>> listPrint([])>>>List processingFunctions that process arbitrarily nested lists can also return values.Exercise 1: Write a function that returns the number of integers in an arbitrarily nested list. It should work as follows:>>> val = countInts([])>>> val0>>> val = countInts([1, 2, 3.5, 'test', 9.1, 10])>>> val3>>> val = countInts([3.5, [[[[1]]], 2], 'five', [[[3, (4, 6)]]]])>>> val3>>> val = countInts([[1, 2], [3, 4], [[[[[[[5]]]]]]], {6, 7}])>>> val5What are the relevant cases? What could the first element be? What do we do in each case?Exercise 2: Write a function that returns the largest in an arbitrarily nested list that contains only non-negative numbers. It should work as follows:>>> val = findMax([])>>> val0>>> val = findMax([1, 2, 3.5, 100, 9.1, 10])>>> val100>>> val = findMax([3.5, [[[[10]]], 2], 5, [[[3, (4, 6)]]]])>>> val10>>> val = findMax([[1, 20], [3.5, 40], [[[[[[[5]]]]]]]])>>> val40What are the relevant cases? What could the first element be? What do we do in each case? ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download