## Snippets tagged recursion

• ### Filtering lists

Two functions showing how to filter functional lists using the specified predicate. First version uses naive recursion and the second one is tail-recursive using the accumulator parameter.

75 people like this

Posted: 13 years ago by Tomas Petricek

• ### Random walk

Create sequence of floating point values generated by random walk process. Functional solution using sequence expressions and yield! construct in a tail-call position.

39 people like this

Posted: 13 years ago by Tomas Petricek

• ### Continuation-Passing Mnemonics

Continuations provide a means whereby heap space can be traded for stack depth (heap space being generally more plentiful than stack depth). They are especially useful where tail recursion is not possible. Here are a couple of simple continuation examples that can be extended to cover more complex scenarios.

100 people like this

Posted: 13 years ago by Neil Carrier

• ### Function to generate all possible combinations where combination "ab" != "ba"

Function to generate all possible combinations where combination "ab" is different then "ba"

6 people like this

Posted: 13 years ago by Ankur Dhama

• ### Split a list

Three ways to split a list in half (but not necessarily in the middle). A forth version added that's very short and should be fast, as we only use List.fold. New champ found.

83 people like this

Posted: 13 years ago by Dmitri Pavlenkov

• ### Combinatorial functions

Here is my F# take on some combinatorial functions from the book "Introduction to Functional Programming" by Richard Bird and Philip Wadler.

5 people like this

Posted: 13 years ago by Cesar Mendoza

• ### Euler #5

Euler #5 solution

4 people like this

Posted: 13 years ago by Michael Falanga

• ### Y(n) Polyvariadic fixpoint

Encoding mutually-recursive functions with a Polyvariadic fixpoint combinator.

5 people like this

Posted: 12 years ago by Nick Palladinos

• ### recursive to dynamic programming with ycombinator

Dynamic programming is equivalent to recursion + some way to remember the results (as far as I undertand) The y combinator allows to "tie" a previously "untied" recursion, which itself allows to compositionally inject additional steps in the recursion. This allows to go from recursion to dynamic programming in a structured way. This exemple is a bit contrived, as there are no overlapping subproblems, which would be the case in more interesting problem (dtw etc..)

3 people like this

Posted: 11 years ago by Nicolas2

• ### Generating a tree from a generic type

I needed a function to generate a tree from a c# class that had some odd semantics, but when I refactored it, I realised almost everyone must have something similar knocking around their codebase, so here's mine.

0 people like this

Posted: 10 years ago by Sean Newham

• ### Palindrom

Check string of palindroms

2 people like this

Posted: 10 years ago by Zhukoff Dima

• ### Retry loop, no tricks

Less-nonsense 8-line retry function that will retry a function a specified up to `maxRetries` times while it throws. After the retries, any remaining exception is allowed to propagate. Accepts a before function to allow you to wait/report when a retry is taking place

2 people like this

Posted: 9 years ago by Ruben Bartelink

• ### Transitive Reduction of a graph

Implements a simple algorithm to compute the transitive reduction of a graph. The transitive reduction of a graph is the minimal set of edges with the same transitive closure

0 people like this

Posted: 8 years ago by Jose Iborra

• ### Recursor

A sugar around IEnumerator<'a> to make it nicer to use with recursive functions

5 people like this

Posted: 6 years ago by manofstick

• ### Step-by-step explanation of the Y combinator

Describes a function called "fix" that can be used to generate recursive functions from non-recursive functions, with some simple examples. (Updated with slightly improved comments.)

9 people like this

Posted: 5 years ago by Brian Berns

• ### Use of Active Patterns to convert integer to Roman numerals

A good use case for demonstrating the use of active patterns

6 people like this

Posted: 4 years ago by Faisal Waris

• ### Rotate or shift lists

This rotates or shifts a list. Unlike http://www.fssnip.net/qY/title/Rotate-List, which runs exponentially, this runs at O(n). In case of overflow (i.e., shift index is larger than the size of the list) will run at most once more with the modulo. This is done to prevent using `List.length` prior to entering the function, as that would lead to a perf punishment of an extra O(n) on each invocation. For large lists, `shift largeList 1` would then get a big performance hit.

1 people like this

Posted: 2 years ago by Abel Braaksma

• ### Projecting lists

Three functions showing how to implement projection for functional lists. First version uses naive recursion and the second one is tail-recursive using the accumulator parameter. The third version extends this with continuation passing.

73 people like this

Posted: 13 years ago by Tomas Petricek

• ### Recursive functions

Show's how to define a recursive function that will calculate a fibonacci number.

16 people like this

Posted: 13 years ago by Robert Pickering

• ### Memoization and Tail Recursive Function

Hi, I expressed Memoization and Memoization Tail Recursive on the functions. I hope something useful.

22 people like this

Posted: 13 years ago by zecl

• ### Project Euler #182

The RSA encryption is based on the following procedure: Generate two distinct primes p and q. Compute n=pq and phi=(p-1)(q-1). Find an integer e, 1 25 people like this

Posted: 13 years ago by Natallie Baikevich

• ### IRC Jokes

Simple snippet that demonstrates recursively defined discriminated unions, the Y combinator (for encoding recursive functions) and recursive processing of tree-like structures

6 people like this

Posted: 13 years ago by Daniel Jackson

• ### Abstraction of the "tail-recursive loop" pattern

A novel, due to performance inadequacy, abstraction of the "tail-recursive loop" pattern. Approaching what a built-in language feature might look like.

3 people like this

Posted: 13 years ago by Stephen Swensen

• ### Random Subset

A function that takes a random subset from a seq<'T>.

1 people like this

Posted: 12 years ago by Taha Hachana

• ### FizzBuzz with Rule Engine

Inspired by http://dave.fayr.am/posts/2012-10-4-finding-fizzbuzz.html Rules are in a list of lambdas that can be easily modified. A pattern-matching recursive function applies them in the correct order.

7 people like this

Posted: 11 years ago by Richard Broida

• ### Combinator for tail-recursive functions

The snippet defines a combinator 'tailrec' that can be used to express tail-recursive functions. If you use 'tailrec' and do not mark your function as recursive, then the function will be a tail-recursive one.

1 people like this

Posted: 11 years ago by Tomas Petricek

• ### Rabbits and Recurrence Relations

One solution to Rosalind rabbits problem.

2 people like this

Posted: 10 years ago by Michel Caradec

• ### Negamax Tic-Tac-Toe

Plays the perfect game of Tic-Tac-Toe using the Negamax algorithm.

2 people like this

Posted: 10 years ago by Richard Dalton

• ### Accumulate a value by applying a function - in two different styles

Two different approaches to the problem of starting with a value, applying a function to it n times, and accumulating a result.

0 people like this

Posted: 8 years ago by Kit Eason

• ### Factorial using Int64, Double and BigInteger

Recursive Factorial using Int64, Double and BigInteger with execution time.

0 people like this

Posted: 7 years ago by Carlos Quintanilla

• ### Seemingly impossible program defines equality between arbitrary functions

It is well known that it is impossible to define equality between arbitrary functions. However, there is a large class of functions for which we can determine equality, and itâ€™s strange and surprising. We explore this idea using F# code translated from the Swift programming language.

3 people like this

Posted: 5 years ago by Brian Berns

• ### Counting Languages - Converting integers to ASTs and back again

This little snippet shows you how you can create a simple recursive data type and define a pair of functions that maps the set of positive integers to unique instances in the AST and back again.

2 people like this

Posted: 5 years ago by Steve Goguen

• ### List2D module

Contains operations for working with 2-dimensional lists.

3 people like this

Posted: 3 years ago by Pavel Tatarintsev