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

learn more… | top users | synonyms

45
votes
4answers
2k 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 ...
52
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 ...
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 ...
2
votes
2answers
171 views

Recursion doesn't happen any more or doesn't happen correctly if I store the recursive relationship in a variable first

I know the following code will form a recursion: Clear["Global`*"] u[i_, n_] := u[i - 1, n] + u[i, n - 1] u[0, n_] := n u[i_, 0] := i u[2, 2] (* => 8 *) But ...
21
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 ...
10
votes
0answers
575 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 ...
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 ...
12
votes
1answer
569 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}}] ...
6
votes
5answers
284 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: ...
23
votes
7answers
823 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 ...
18
votes
4answers
867 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 ...
9
votes
1answer
874 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 ...
1
vote
1answer
144 views

Bounded random walk

I have a random walk algorithm that I want to implement, but I am getting a recursion depth issue. I am making a list of points that Z particles can be in over the ...
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 ...
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 ...
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) & ...
7
votes
3answers
486 views

Nested list to graph

The following nested list can be regarded as a representation of a (tree) graph: ...
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 ...
11
votes
2answers
454 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 ...
6
votes
1answer
278 views

How to deal with too much recursion

I have put together a very simple climate model based around four equations which define the state at time t based on time t-1, ...
4
votes
1answer
734 views

How do I use RSolve to solve a system of recurrence relations?

I am trying to solve a system of recurrence relations as follows. ...
6
votes
2answers
318 views

Update a function avoiding infinite recursion

I am quite new to Mathematica and not completely familiar with functional programming. I am currently working with a function (call it foo) and wish to change its behaviour, for example, by adding 1 ...
4
votes
3answers
509 views

How to solve an integral equation by iteration method? [duplicate]

How I can obtain $n^{th}$ approximation of the following equation $f(t)=t+\int_0^tds f(s)$ by iteration method?
3
votes
4answers
866 views

Recursive function for calculating the arithmetic mean of a vector

I want to write recursive function for calculating the arithmetic mean of a vector. For $X(n)=\{1,2,3,\ldots, n\}$, the formula is ${\rm Mean}(X(n))=((n-1)\, {\rm Mean}((X(n-1))+X_n)/n$. My ...
3
votes
2answers
424 views

Nonlinear recurrence relation

I entered the following recurrence relation into RSolve and it just gave the question back to me. $$a_{n+1} = \frac{(1+a_n +(a_{n−1})^3)} 3$$ Is there another way to get a formula for the nth term?
2
votes
2answers
123 views

Recursion problem

I try to make designation a = {Subscript[a,1], Subscript[a,2], Subscript[a,3]} but receive mistake $RecursionLimit::reclim: Recursion depth of 1024 ...
1
vote
1answer
75 views

Implementation of a recursive function [duplicate]

I have been trying to implement a recursive function, but still struggle. Here's what I have written: ...
0
votes
1answer
160 views

Explicit, closed formula for recursive integral as a function of the recursive parameter

This is a follow-up of this question/answer. I'm working on a recursive integral more complicated than the one on the linked question, but this one can be used as an example. I would like to obtain ...
6
votes
1answer
368 views

Speeding up the non-negativity algorithm for multilinear function with interval probabilities?

The algorithm is a branch-and-bound algorithm that calculates the non-negativity of a multilinear function with interval probabilities. The lines 9-11 has an optimization that is explained on the ...
12
votes
3answers
248 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) & & ...
10
votes
2answers
428 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$$ ...
8
votes
2answers
312 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): ...
9
votes
4answers
540 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 ...
6
votes
2answers
396 views
5
votes
4answers
233 views

Recursive piecewise integral relation with piecewise base case?

How is this recursive formula $$ f_{n+1}(z) = \int_0^1 f_{n}(z-y)\,{\rm d}y $$ implemented in Mathematica? The base case is $$ f_1(z) = \begin{cases} 1 & 0\leq z\leq 1 \\ 0 & ...
5
votes
1answer
259 views

Compile, “global variables” and recursion

I am trying to do something similar to this, namely to make a Compile'd function outer that itself calls a ...
3
votes
3answers
204 views

Pare down list recursively

What is the best way to pare down a list whereby the $n$th number is removed from the list recursively? This ...
3
votes
1answer
1k views

Solve pair of recurrence relations

[Corrected equations and added simple example] Can you solve a system of (loosely) coupled recurrence relations like this in Mathematica somehow? ...
3
votes
1answer
250 views

Avoid crash in recursive Dynamic

With the following Dynamic cell, I can reproducibly crash Mathematica, so do not try this unless you have saved all your work! ...
2
votes
1answer
114 views

Kernel crashed after $RecursionLimit = Infinity

$RecursionLimit = Infinity; T[n_, k_]:= T[n, k] = If[n == 0 || k == 1, 1, T[n, k-1] + If[n<k, 0, T[n-k, k]]]; Table[T[n!, n], {n, 1, 9}] Without ...
2
votes
1answer
592 views

Finding n-th term of a sequence of functions

Lets say, I have the following series of functions, $f_1=a+1$ $f_2=a^2+2a+1$ $f_3=a^3+3a^2+3a+1$ Assume that $f_4, f_5,$ and $f_6$ are also known. However $f_n$ is not known as a function of $n$. ...
11
votes
2answers
285 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 ...
8
votes
5answers
354 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 ...
7
votes
1answer
234 views

How to find a recurrence relation for a sequence?

I have a sequence given by an explicit formula for n-th term: ...
5
votes
2answers
447 views

Plotting two recursive functions

I'm trying to plot two recursive functions (p and θ) on a map. So far I have: ...
5
votes
2answers
1k views

How to find a recurrence relation for a numerical sequence?

This question was inspired by Vladimir Reshetnikov's question (How to find a recurrence relation for a sequence?): Given a finite sequence of numbers, how can we find in MMA a recurrence relation ...
5
votes
1answer
256 views

Setting $RecursionLimit crashes Mathematica 10

I have encountered what I shall presume is a bug: setting $RecursionLimit repeatably crashes the Mathematica 10 kernel: ...
5
votes
4answers
299 views

Can the general term my recurrence equations be written with Floor or Mod?

I want to know the formula for the general term of the following recurrence system. I guess it can be written with Floor or Mod. ...
5
votes
1answer
298 views

Build recursion in parallel?

Problem Let's define a simple recursion. f[1] = 1; f[n_] := f[n] = f[n - 1]*n; If I evaluate f in parallel ...
4
votes
0answers
76 views

Method of characteristics, recursion formulas

I'm helping a friend out with a problem. He needs to plot out the solution to a water surge in a pipeline. I have all the parameters set and I've put the equations in Mathematica, but I can't get the ...