CS 149

Professor: Alvin Chao

• Tonight Reading Wk 12
• Wed 11pm PA2B Code
• Thu Actual Quiz 5 in class

Definitions

• Recurrence Relation:
• A relation between successive values of a function that allows the systematic calculation of values, given an initial value
• Recursion:
• Formal - Computation using a recurrence relation
• Informal - A function is recursive (or "uses recursion") if it calls itself

​

Recursion

Thinking recursively is easy if you can recognize a subtask that is similar to the original task. - Horstman Big Java ���Humorous quote:

There are two kinds of people in the world, those who divide the world into two kinds of people and those who do not

​

What do these have in common?

• One Answer:
• The definition/object/action involves the definition/object/action itself.
• ​
• Another Answer:
• Refinement/Nesting/"Looking Deeper"

​

Using Recursion in definitions: Factorial

• The Concept:
• A function is defined recursively if the value of the base cases are given (e.g., f(0) is given) and the value of f(n) is given in terms of
• f(n−1) for the other cases (e.g., for n>0)
• ​
• An Example - A Recursive Definition of the Factorial:
• 0!=1 (i.e., f(0)=1)
• n!=(n−1)!⋅n for n>0 (i.e., f(n)=f(n−1)⋅n for n>0)
• ​

​

​

Example: Fibonacci Numbers

• Another Example - Fibonacci Numbers:F(0)=0
• F(1)=1
• F(n)=F(n−1)+F(n−2) for n>1
• ​
• Fibonacci Numbers - Some Things to Note:
• There is more than one base case
• The function calls itself from more than one place (making it more complicated and inefficient than it seems at first glance)

​

Recursion

”In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120.” Source: https://en.wikipedia.org/wiki/Factorial

1. Consider how to calculate 4! = 24.
1. Write out all the numbers that need to be multiplied: �4! =
2. Rewrite the expression using 3! instead of 3 × 2 × 1: �4!
2. Write an expression similar to #1b showing how each factorial�can be calculated in terms of a simpler factorial.
• 3! =
• 2! =
• 100! =
• n! =
3. What is the value of 0! based on the model? Does it make sense to define 0! in terms of a simpler factorial? Why or why not?

​

If we repeatedly break down a problem into smaller versions of itself, we eventually reach a basic problem that can’t be broken down any further. Such a problem, like 0!, is referred to as the base case.

​

​

​

Factorial with loops

Recursion Trace

Recursion Trace questions

• a) What specific method is invoked on line 7?
• b) Why is the if statement required on line 3?

​

Designing Recursive Algorithms

• Identifying the Base Case:
• What is (are) the easy cases(s)? In other words, what case(s) can I solve trivially?
• ​
• Refining the Difficult Cases:
• How can I refine/reduce a difficult case to make it easier? In other words, how can I make progress?

​

Recursion - Factorials

• A function that invokes itself is called recursive. What two steps were necessary to define factorial? How were they implemented in Python?
• 7. How many distinct function calls would be made to factorial to compute the factorial of 3? Identify the value of the parameter n for each of these separate calls.
• 8. Here is the complete output from the program in #5. Identify which distinct method call printed each line. In other words, which lines were printed by factorial(3), which lines were printed by factorial(2), and so on.
• 9. What happens if you try to calculate the factorial of a negative number? How could you prevent this bug in the factorial function?

Fibbonacci numbers

The Fibonacci numbers are a sequence where every number (after the first two) is the sum of the two preceding numbers: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . .

Source: https://en.wikipedia.org/wiki/Fibonacci_number

We can define a recursive function to compute Fibonacci numbers. Enter the following code into a Python Editor, and run the program to see the sequence.

​

fibonacci

Questions

• a) How many function calls are needed to compute fibonacci(3)? Identify the value of the parameter n for each of these calls.�
• b) How many function calls are needed to compute fibonacci(4)? Identify the value of the parameter n for each of these calls.�
• c) How many function calls are needed to compute fibonacci(5)? Identify the value of the parameter n for each of these calls.

​

Summation

”In mathematics, summation (capital Greek sigma symbol: Σ) is the addition of a sequence of numbers; the result is their sum or total.”

100�∑i = 1+2+3+...+100 = 5050 i=1 Source: https://en.wikipedia.org/wiki/Summation�

Consider how to calculate ∑ i = 10.

​

a) Write out all the numbers that need to be added:

1+2+3+4

b) Show how this sum can be calculated in terms of a smaller summation.

N + sum of i for n-1

What is the base case for the summation? i = 1

​

​

​

Recursive summation

def summation(n):

if n == 1:

​

return 1

else:

​

return n + summation(n - 1)

​

​

Recursion tracing

https://recursion.vercel.app/

PI Question

PI Nov 11 Tue

Tests for PA2B

[L] (N) _N_ (T) [N] a b c d e

_ _E_ _ _S_ _N_ f h j

(I) _I_ [O] _U_ (A) k l m n o

_ _R_ _ (S) _O_ p r t

[D] _W_ (G) _K_ [Y] u v w x y

Starter file text:

[L],(N),_N_,(T),[N]

___,_E_,___,_S_,_N_

(I),_I_,[O],_U_,(A)

___,_R_,___,(S),_O_

[D],_W_,(G),_K_,[Y]

​

​

Solution file text:

[L],[O],[G],[I],[N]

[I],[_],[R],[_],[A]

[K],[N],[O],[W],[N]

[E],[_],[S],[_],[N]

[D],[U],[S],[T],[Y]

​

​

​

U] (A) (E) _O_ [T] a b c d e

_L_ _ [H] _ _K_ f h j

(L) _E_ [U] (E) (K) k l m n o

(P) _ _N_ _ (A) p r t

[T] _C_ (S) _S_ [N] u v w x y

Starter file text:

[U],(A),(E),_O_,[T]

_L_,___,[H],___,_K_

(L),_E_,[U],(E),(K)

(P),___,_N_,___,(A)

[T],_C_,(S),_S_,[N]

​

​

Solution file text:

[U],[N],[S],[E],[T]

[P],[_],[H],[_],[A]

[S],[K],[U],[L],[L]

[E],[_],[C],[_],[O]

[T],[A],[K],[E],[N]

​

​

• Acknowledgements

Parts of this activity are based on materials developed by Chris Mayfield and Nathan Sprague.

</end>