18656 Functional Programming in Practice Week 3

This Note contains:

• Recursion

• Recursion
  • Syntax
  • Anatomy of safe recursion
  • Recursive with Lists
    • Exercise #1
      • Solution
    • Exercise #2
      • Solution
    • Reflection
  • Recursion and memory management
    • Tail Recursion
      • Limitations

Recursion

Calling of a function within itself, usually with a different input.

A core technique used in functional programming instead of loops

• Problem broken into small part
• Easy to understand code repeat over and over

Syntax

rec keyword is used to define recursive expressions.

let rec fib n =
	if n <= 2 then 1
	else fib(n - 1) + fib(n - 2)

rec allows to use a bound name within its definition.

Practice: Refactor is function to pattern-matching

let rec fib n =
	match n with
	| 1 | 2 -> 1
	| _ -> fib(n - 1) + fib(n - 2)

Anatomy of safe recursion

Base case allows the recursion to stop

• recursive call is absent from it
• require a clear stop condition (empty collection, countdown, etc.)

Recursion cases allows the recursion to continue

• describes …

Generic structure of a recursive function in F#:

let rec funcname input =
	match expr with
	| basscase_pattern ->
		basecase_expression
	| recursive_pattern ->
		recursive_expression

• One or more of each case type is necessary

what would happen if a recursive function does not have a base case, or never executes it?

It would go into an infinite loop

In an infinite loop, could a recursive function ever stop?

• Whenever it turns out. ..

Each recursive call should make progress toward the base case

• one of the arguments should get smaller
• never make a recursive call with the same parameters you were given

Recursive with Lists

Reminder: List is a combination of its head and tail

• Recursive case: tail

• Progress toward the base case: head

• Base case: empty list

Exercise #1

Implement a function that sums a list of elements recursively:

• Use match expression on the list argument
• Use head, tail and empty List

Solution

let rec sumOfList list = 
	match list with
	| head :: tail -> head + sum tail // the sum is the return value of each recursive functoin call
	| [] -> 0 // Recursion stops; the sum are propagated

Exercise #2

Write a recursive function that accepts a list and a predicate to determine if the item belongs to the resulting list:

• Use match expression on the list argument

• Hint: use pattern matching guards

• Call the function on a List [1; 2; ...; 10] with a predicate that checks if a number is even

Solution

let rec applyPredicate list predicate = 
	match list with
	| [] -> list
    | head :: tail when predicate head -> head :: applyPredicate tail predicate // resulting list is built using cons operator and the element matching predicate function and recursive call with remaining elements
    | _ :: tail -> applyPredicate tail  predicate // matches any head element checked when predicate evaluates to false
    
let result = applyPredicate [1 .. 10] (fun x -> x % 2 = 0)

Reflection

Consider imperative and funcional approaches to the filtering function, wo is managng the state?

• imperative version: developer
• functional version: F# compiler

Recursion and memory management

Many programming language are not optimized for recursion

• For every function call a new stack frame is allocated
• The operation takes up space and time
• Large number of recursive call can cause stack overflow
• Typically, recursion is slower that iteration.

.Net Common language Runtime supports tail recursion.

• Technique improving efficiency
• When a recursive al is the last call in the function, runtime replaces …

Tail Recursion

Tail-Call optimization transforms tail-recursive function calls into optimized loops

Limitations

F# compiler can perform tail call optimazation under certain conditions

The recursive call must be the final action of the function

• It cannot be followed by any additional computations or expressions
• it must return the result of the function directivity

• 本文作者： Depasinre
• 本文链接： https:/Depasinre.github.io/2024/02/02/18656-week3/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！