Cap 5: Recursion

Cap 5: Recursion

1. Recursion is actually a way of defining functions in which the function is applied inside its own definition

   • Definitions in mathematics are often given recursively
     • the edge condition and is important if you want your recursive function to terminate

2. Examples

   • Fibonacci
     • First: put the edge condition
       • F (0) = 0 y F (1) = 1,
     • Make the recursion
       • F (n) = F (n-1) + F (n-2)
   • The maximum function
     • first set up an edge condition
       • that the maximum of a singleton list is equal to the only element in it
       • hen we can say that the maximum of a longer list is the head if the head is bigger than the maximum of the tail
       • If the maximum of the tail is bigger, then it's the maximum of the tail
     • use pattern matching to split a list into a head and a tail.
     • use a where binding to define maxTail as the maximum of the rest of the list
     • check if the head is greater than the maximum of the rest of the list. If it is, we return the head

3. Thinking recursively

   • Usually you define an edge case
     • is some scenario where a recursive application doesn't make sense
   • define a function that does something between some element and the function applied to the rest

Bilder und Dateien der Mindmap