Recursion Examples
Recursion Examples
Recursion (review)
Recursion (review)
Recursion (review) Scenario:You are waiting in line for a concert.You can't see the front of the line,but you want to know your place in the line. The person at the front,knows they are at the front! Base case You ask the person in front of you:"what is your Recursive call place in the line?” When the person in front of you figures it out and Use the solution to tells you,add one to that answer. the smaller problem
Recursion (review) Scenario: You are waiting in line for a concert. You can't see the front of the line, but you want to know your place in the line. Base case Recursive call Use the solution to the smaller problem You ask the person in front of you: “what is your place in the line?” When the person in front of you figures it out and tells you, add one to that answer. The person at the front, knows they are at the front!
Iteration vs.Recursion Iteration and recursion are somewhat related ● Converting iteration to recursion is formulaic,but converting recursion to iteration can be more tricky Iterative Recursive def fact_iter(n): deffact(n): total,k=1,1 ifn==0: whilek <n: return 1 total,k total*k,k+1 else: return total return n*fact(n-1)】 m n!=Ik nn(n-1)!otiherwise if n 0 k=1 Names:n,total,k,fact_iter Names:n,fact
Iteration vs. Recursion ● Iteration and recursion are somewhat related ● Converting iteration to recursion is formulaic, but converting recursion to iteration can be more tricky def fact_iter(n): total, k = 1, 1 while k <= n: total, k = total*k, k+1 return total def fact(n): if n == 0: return 1 else: return n * fact(n-1) Iterative Recursive Names: n, total, k, fact_iter Names: n, fact
Sum Digits Let's implement a recursive function to sum all the digits of 'n'. Assume 'n'is positive. def sum_digits(n): """Calculates the sum of the digits 'n'. 1.One or more base >>sum_digits(8) cases 8 sum_digits(18) 2.One or more >>> 9 recursive calls >>> sum_digits(2018) with simpler 11 arguments. I 1 II ”大*火 YOUR CODE HERE 3.Using the +*★” recursive call to solve our larger problem
Sum Digits Let’s implement a recursive function to sum all the digits of `n`. Assume `n` is positive. def sum_digits(n): """Calculates the sum of the digits `n`. >>> sum_digits(8) 8 >>> sum_digits(18) 9 >>> sum_digits(2018) 11 """ "*** YOUR CODE HERE ***" 1. One or more base cases 2. One or more recursive calls with simpler arguments. 3. Using the recursive call to solve our larger problem