Share
Embed
Transcript
30 slides
-
Programming basics • Variables and scope • Control structures (conditionals,
loops) • Functions (with return statement) -
A classical example - factorial n! {1 1 × 2
× … × (n-1) × n if n = 0 if n > 0 Intuitive definition -
A classical example - factorial n! {1 1 × 2
× … × (n-1) × n if n = 0 if n > 0 Intuitive definition (n-1)! -
A classical example - factorial n! {1 n × (n-1)!
if n = 0 if n > 0 Recursive definition n! {1 1 × 2 × … × (n-1) × n if n = 0 if n > 0 Intuitive definition (n-1)! -
Unrolling the function calls fact(4) ⤷ return 4*fact(3) ⤷ return
3*fact(2) ⤷ return 2*fact(1) -
Unrolling the function calls fact(4) ⤷ return 4*fact(3) ⤷ return
3*fact(2) ⤷ return 2*fact(1) ⤷ return 1*fact(0) -
Unrolling the function calls fact(4) ⤷ return 4*fact(3) ⤷ return
3*fact(2) ⤷ return 2*fact(1) ⤷ return 1*fact(0) ⤷ return 1 -
Unrolling the function calls fact(4) ⤷ return 4*fact(3) ⤷ return
3*fact(2) ⤷ return 2*fact(1) ⤷ return 1*fact(0) ⤷ return 1 㽉 1 -
Unrolling the function calls fact(4) ⤷ return 4*fact(3) ⤷ return
3*fact(2) ⤷ return 2*fact(1) ⤷ return 1*fact(0) ⤷ return 1 1 㽉 㽉 1 -
Unrolling the function calls fact(4) ⤷ return 4*fact(3) ⤷ return
3*fact(2) ⤷ return 2*fact(1) ⤷ return 1*fact(0) ⤷ return 1 1 㽉 1 㽉 㽉 1 -
Unrolling the function calls fact(4) ⤷ return 4*fact(3) ⤷ return
3*fact(2) ⤷ return 2*fact(1) ⤷ return 1*fact(0) ⤷ return 1 1 㽉 1 㽉 㽉 2 㽉 1 -
Unrolling the function calls fact(4) ⤷ return 4*fact(3) ⤷ return
3*fact(2) ⤷ return 2*fact(1) ⤷ return 1*fact(0) ⤷ return 1 1 㽉 1 㽉 㽉 2 6 㽉 㽉 1 -
Unrolling the function calls fact(4) ⤷ return 4*fact(3) ⤷ return
3*fact(2) ⤷ return 2*fact(1) ⤷ return 1*fact(0) ⤷ return 1 1 㽉 1 㽉 㽉 2 24 6 㽉 㽉 1 -
Definition of a recursive function Base case the result is
the simplest version of the problem Recursive case the result is computed based on a reduced version of the same problem -
Definition of a recursive function Base case the result is
the simplest version of the problem Recursive case the result is computed based on a reduced version of the same problem n! {1 n × (n-1)! if n = 0 if n > 0 -
Definition of a recursive function Base case the result is
the simplest version of the problem Recursive case the result is computed based on a reduced version of the same problem n! {1 n × (n-1)! if n = 0 if n > 0 Base case Recursive case -
Cumulative return An investment returns 2.5% every year. If you
invest $1000 at the beginning only, how much money do you get after n years of cumulating the interests? agg(n) { Base case Recursive case -
Cumulative return An investment returns 2.5% every year. If you
invest $1000 at the beginning only, how much money do you get after n years of cumulating the interests? agg(n) {1000 agg(n-1) × 1.025 if n = 0 if n > 0 Base case Recursive case -
Another classical example - Fibonacci (rabbits) fib(n) {1 1 fib(n-1)
+ fib(n-2) if n = 0 if n = 1 if n > 1 Base case Base case Recursive case -
Another classical example - Fibonacci (rabbits) Rabbits Newly born Total
month 0 0 1 1 month 1 1 0 1 month 2 1 1 2 month 3 2 1 3 month 4 3 2 5 month 5 5 3 8 month 6 8 5 13 -
Another classical example - Fibonacci (rabbits) fib(n) {1 1 fib(n-1)
+ fib(n-2) if n = 0 if n = 1 if n > 1 Base case Base case Recursive case Rabbits Newly born Total month 0 0 1 1 month 1 1 0 1 month 2 1 1 2 month 3 2 1 3 month 4 3 2 5 month 5 5 3 8 month 6 8 5 13 -
Palindrome A palindrome is a sequence of characters which reads
the same backward or forward. “kayak” “emma” -
Palindrome A palindrome is a sequence of characters which reads
the same backward or forward. pal(s) ➡ True if the length of s is 0 or 1 ➡ False if the first and last characters do not match (assuming the length is greater than 1) ➡ pal(s’) otherwise, considering s’ the substring of s without the first and last character Base case Recursive case Base case “kayak” “emma” -
Recursion is about problem solving Recursion is a way to
solve problems and design solutions ➡ Programming paradigm : functional programming -
Going further • Recursive data structures list, tree, graph, …
• Puzzles tower of Hanoi, Sudoku, … • Art Fractales image sources wikimedia and Deviant Art