For questions about defining recursive functions, recursive algorithms and solving recursive equations.

learn more… | top users | synonyms

53
votes
2answers
10k views

How can I use Mathematica's graph functions to cheat at Boggle?

Boggle is a word game played with 16 dice and a 4x4 tray. This question is inspired by a Stack Overflow question about Boggle that I decided to solve using Mathematica. In addition to Mathematica, I ...
45
votes
4answers
3k views

How can I implement dynamic programming for a function with more than one argument?

Dynamic programming is a technique for avoiding the repeated computation of the same values in a recursive program. Each value computed is immediately stored. If the value is needed again, it is not ...
29
votes
3answers
2k views

Smooth Peter de Jong attractor

Today I was playing with Peter de Jong attractor. At the bottom of the page I've linked there are beautiful examples like: My attempts are not so great: It is around 10^5 points. For more than 5*...
29
votes
4answers
1k views

What tools can help in realizing tail recursion?

I had nice discussions with Leonid and Rojo that got me interested in tail recursion. Tail recursion is not always easy to realize with Mathematica, so it would be nice to have some tools to help with ...
26
votes
3answers
1k views

How to clear parts of a memoized function?

I have a function of two variables, e.g.: f[a_, b_] := f[a, b] = something f[a - 1, b - 1] etc With the above code I used the concept of memoization to speed up ...
24
votes
7answers
845 views

Alternative ways to implement a triangular recursion

Triangular recursions are a class of algorithms that frequently turn up in computational mathematics. These recursions are expressible in the general form $$T_k^{(n)}=f(T_{k-1}^{(n)},T_{k-1}^{(n+1)})$...
23
votes
3answers
1k views

Visualisation of a recursive function

Is there a way to nicely visualize recursive functions? (diagrams/plots) More specifically I'm looking for a way to make contrast (visually) between e.g. the cosine function which if continuously ...
18
votes
6answers
870 views

Recursively appending elements to a list

In wanting to demonstrate the power of Mathematica, I wanted to show my 11-year-old son how we could validate that his sequences homework was correct. We could generate the next value in sequence in a ...
18
votes
4answers
916 views

How to define a recursive pattern?

I want to translate this recursive syntactic definition into a Mathematica pattern1: $$ \mathtt{x}: \begin{cases} \text{Null}\\ \{\textit{integer}, \mathtt{x}\} \end{cases} $$ In other ...
15
votes
6answers
803 views

How can I evaluate only a single step of a recursive function?

Let's say have a simple recursive function for the Fibonacci sequence f[0] := 1 f[1] := 1 f[n_] := f[n - 1] + f[n - 2] but I want to see how it will expand in a ...
14
votes
3answers
340 views

Mimic a procedural, recursive clustering algorithm for site percolation using functional programming

Sorry in advance for my logorrhea: I just want to make sure all of the information is here. Context and Question I am investigating site percolation on a square lattice. I have a working, depth-...
14
votes
1answer
613 views

How can I define a Listable function only apply to a vector?

Consider the function f which should behave as f[{{1, 2}, {3, 4}, {5, 6, 7}}] ...
13
votes
7answers
428 views

Concatenation of lists in a Fibonacci-like pattern

I am trying to create a List of elements that follow the general pattern: $$X_{n+1} = X_n X_{n-1}$$ where the operation on the right hand side is concatenation, i.e., joining. I want to achieve the ...
13
votes
3answers
453 views

ToExpression fails with long nested string expressions

Consider the following conversion from String to Mathematica Expression: ...
12
votes
2answers
313 views

Can RecurrenceTable make use of CompiledFunction?

I'm trying to implement a discrete-time 2D Verlet algorithm for a point-mass subject to a softened gravitational interaction as a test for a more computationally intensive simulation using ...
12
votes
3answers
256 views

How to implement a more efficient inverse triangular recursion?

Consider the following inverse triangular formula $$\left( \begin{array}{ccccc} & & & & N_{i-p,p}\left(u_0\right) \\ & & N_{i-2,2}\left(u_0\right) & & ...
11
votes
7answers
3k views

Recursive function with if-statement

I am trying to represent the following function definition in Mathematica: $$\begin{align*} f(1)&=1 \\ f(2n)&= \begin{cases}f(n) & \text{if}\space n\equiv0\pmod{2} \\ 2f(n) & \text{if}...
11
votes
5answers
1k views

How to deal with recursion formula in Mathematica?

In engineering problems, I am always seeing many recursion formula. For instance, In the book "The NURBS book", I discovered many recursion formula Fibonacci $$f(...
11
votes
2answers
460 views

How to deduce a generator formula for a polynomial sequence?

Consider a polynomial sequence $\{p_n\}$ generated by some (simple) rule: $$ \begin{array}{l} p_1(x)=x \\ p_2(x)=2 x-x^2 \\ p_3(x)= x^3-3 x^2+3 x \\ p_4(x)=-x^4+4 x^3-6 x^2+4 x \\ p_5(x)= x^5-5 x^4+...
11
votes
2answers
298 views

How to “inform” successive ContourPlot calculations?

I need to draw some contour plots of very non-linear functions. As a simple example, take a Mandelbrot Set divergence contour near $z\approx i$. (Just to be clear, I'm not trying to write a ...
11
votes
2answers
2k views

How can I solve a difference-differential equation?

How do I ask Mathematica to try to solve a recursive relation that defines a sequence of functions? For example, suppose I know that $g_n(x) = g_{n-1}'(x)$ for $n > 0$ and that $g_0(x) = e^{2x}$. ...
10
votes
9answers
2k views

How can I make a Tribonacci sequence in the form of a list?

How can I make a Tribonacci sequence that is in listing form? it suppose to look like the Fibonacci sequence but I couldn't get ...
10
votes
4answers
552 views

Partitioning a list by recursion (Programming Paradigms via Mathematica (A First Course))

I am working through the course Programming Paradigms via Mathematica. One of the homework exercises for the section Recursion I: Passing the Buck is as follows: Use recursion to partition a list:...
10
votes
4answers
343 views

Order items by closest to the previous

I have a list of 2D points (a table, imagine the data of a parametric plot shuffled) I would like to join the points with a line that starts from one of them and always goes to the closest one. I ...
10
votes
2answers
448 views

Recursive Integral for Volume of $n$-Ball

The volume of an $n$-ball (the $(n+1)$-dimensional analogue of a disk) of radius $r$ can be found by the following integral recurrence: $$V_0(r)=2r$$ $$V_n(r)=\int_{-r}^rV_{n-1}\left(\sqrt{r^2-x^2}\...
10
votes
1answer
1k views

Efficient backtracking with Mathematica

Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("...
10
votes
0answers
589 views

Compile recursive function modifying global variables

How to compile recursive formula when it relies on more than a few global variables (global to the topmost compiled function)? It is unreasonable to pass on all such variables to each recursive ...
9
votes
2answers
571 views

Improve speed in this tree - memoization won't suffice

I have two functions, one of which calls the other. I need to do some calculations but I was unable to optimize my code to do it efficiently. In search I came across the memoization technique, which ...
9
votes
1answer
893 views

Compiling a recursive formula

My question is related to computing what is called "invariant measure" for a particular well known fractal - the Sierpinski triangle. We have an array m of four two by two matrices, say ...
9
votes
1answer
148 views

Maximizing a recursive functional equation

I would like to maximize a recursive functional equation but I am struggling with setting up the problem correctly. The equation I am interested in captures the nature of a decision process over time ...
9
votes
1answer
108 views

What do RecursionLimit and IterationLimit actually set?

The following recursive functions respectively calculate the length of a Short-cut Collatz Conjecture series and perform a pointless demonstration recursion: ...
9
votes
2answers
132 views

Evaluating summations involving Fibonacci numbers in terms of Fibonacci numbers

There are many summations involving Fibonacci numbers which Mathematica 10.4 is able to evaluate directly in terms of Fibonacci numbers. For example, Mathematica evaluates the summation given below as ...
8
votes
5answers
362 views

Wrapping a function in count

I am working through the Programming Paradigms via Mathematica (A First Course) and am attempting to answer the following: Use recursion to count how many times the argument can have its square ...
8
votes
2answers
316 views

Recursive partitioning: Is there a better way to do this?

Consider the following function, which recursively splits a list into equal length sublists (the length of the list is assumed to be a power of the second argument): ...
7
votes
4answers
761 views

Implementing Picard's Iteration for solving ODEs

Picard's Iteration is a way of solving the IVP $$y'(x)=f(x,y(x)), \quad y(x_0)=y_0 $$ It consists of defining the following sequence of functions recursively: $$y_0(x):=y_0 \\ y_{n}(x):=y_0+\int_{...
7
votes
2answers
125 views

Recursive function activity

We had the following question on an activity for our students: Let $f_0(x)=x+|x-100|-|x+100|$, and for $n\geq 1$, let $f_n(x)=|f_{n-1}(x)|-1$. For how many values of $x$ is $f_{100}(x)=0$? When I ...
7
votes
2answers
151 views

Recursive function with array of variables

I am trying to create a recursive function which works with an increasing array of variables. Since the formula is quite complex, i will try to simplify my example to the core of my problem. The ...
7
votes
3answers
242 views

Deleting any list that contains a negative number

We had another nice question in a student activity today. The increasing sequence of positive integers $a_1,a_2,a_3,\ldots$ has the property that $$ a_{n+2}=a_n+a_{n+1} \text{ for all } n\ge 1. $$ ...
7
votes
2answers
212 views

Solving with DSolve recursively

I need to find $f(x,n)$ in the interval [0,1] defined by recursion, \begin{equation} \frac{d f(x,n+1)}{dx} = f(x,n) \end{equation} with boundary conditions $f(0,n+1) = 1$ and $f(x,0)=1+ x $ Using ...
7
votes
2answers
788 views

How can I define a sequence of functions?

I need to define a function fun, and then re-define this function iteratively. The code is given at the end. First, a function ...
7
votes
3answers
526 views

Nested list to graph

The following nested list can be regarded as a representation of a (tree) graph: ...
7
votes
2answers
261 views

How to compile self-referencing functions (to perform recursive a task)

How do I compile a self-referencing function to perform iterative tasks? The naive approach doesn't seem to work. Here is a simple example to illustrate the problem: ...
7
votes
1answer
329 views

Setting $RecursionLimit across all parallel kernels

I'm trying to optimize an elliptic curve factoring method by running it in parallel. There is a recursive step which required me to set the recursion limit higher than 256, however when I try and run ...
7
votes
1answer
244 views

How to find a recurrence relation for a sequence?

I have a sequence given by an explicit formula for n-th term: ...
7
votes
1answer
734 views

Demonstrating Ackermann's Function

The Ackermann function is an extremely fast growing function. There are some slightly different versions of the function, but the one that I am looking for can be defined as: $$ A_0(x)=x+1 \\ A_{k+1}(...
7
votes
1answer
402 views

Second order differential equation with boundary conditions solving repeatedly

I want to solve a second order differential equation in the interval[-1:1], which does not have a analytic solution, \begin{eqnarray} y''(x) &=& k \phi^2(x)y(x) \\ \phi(x) &=& \frac{1}{...
7
votes
1answer
159 views

Recurrences of lists

Assume we have a multi-dimensional recurrence, e.g. $\qquad\begin{align*} a_1 &= (1,2) \\ a_n &= (1,2) + a_{n-1} \quad, n>1 \end{align*}$ with the easy solution $a_n = (n,2n)$. How ...
6
votes
4answers
596 views

Paying off an installment

How do I determine the weekly installment I have to pay, if my loan is, let's say, loan=5000, with interest rate of 2% every ...
6
votes
5answers
285 views

How to nest my own “times” function to get powers

I have a "times" function. I'd like to create a power function using it. It should look like this for an 6th power: ...
6
votes
3answers
842 views

Implementing the Farey sequence efficiently

There is of course the silly implementation: FareySequence[n_] := Union[Flatten[Table[j/i, {i, 1, n}, {j, 0, i}]]] However, there are numerous properties and ...