1

I need to implement a recursion function which will provide the first N elements of a sequence, x_{n+1} = r*x_n*(1-x_n). The code I present below is not running, the error being if N == 0: RecursionError: maximum recursion depth exceeded in comparison. I will appreciate your help in making the code run.

def sequence(N, x0, r):
    A = [x0]
    if N == 0:
        return x0
    else:
        A.append(r * sequence(N, x0, r) * (1 - sequence(N, x0, r)))
    return [A[i] for i in range(N + 1)]


print(sequence(10, 2, 2))
Improve this question
1
  • You always pass N as-is to the recursive calls of sequence(), so there's no way you could ever reach if N == 0 if you originally pass in a non-zero N. Commented Oct 2, 2022 at 11:55

2 Answers 2

Reset to default
1

Staying as close as possible from your initial try, I would do something that also returns a sequence, not a number

def sequence(N, x0, r):
   A=[x0]
   if N==0:
      return A
   else:
      return A + sequence(N-1, r*x0*(1-x0), r)

print(sequence(10, 2, 2))

Explanation: it computes the first element of the sequence, and then the rest of it, recursively.

Just trace it for a few values.

For N=0

Simple, it just returns [x0]

For N=1

For clarity (otherwise, x0 means different things during recursions), let's choose x0 for the initial call=2, and also (even if r stays the same thorough all call), choose r=3. So let's call sequence(1,2,3)

  • In sequence(1,2,3) call, we starts by A=[2]
  • Then, since N≠0, we go to else, so we compute A=[2]+sequence(0,3*2*(1-2),3) recursively, that is sequence(0,-6,3)``
    • In this sequence(0,-6,3) call, we starts with A=[-6]
    • Since N=0 in this call, we simply return A, aka [-6]
  • So, back in sequence(1,2,3), we return A+result of recursive call sequence(0,-6,3). That is A+[-6]. That is [2]+[-6]
  • so final answer is [2, -6]

For N=2

(And still initial x0=2, and r=3)

  • In sequence(2,2,3) call, we start with A=[2]
  • Since N=2≠0, we return A+sequence(N-1,r*x0*(1-x0), r), and for that we need to compute sequence(1, -6, 3) recursively
    • In sequence(1,-6,3) call, we start with A=[-6]
    • Sine N=1≠0, we return A+sequence(N-1,r*x0*(1-x0),r) that is [-6] + sequence(0, 3*(-6)*7, 3) = [-6] + sequence(0, -126, 3).
    • so we have to call recursively sequence(0, -126, 3).
      • In sequence(0, -126, 3), we start we A=[-126]
      • Since N=0, we just return that [-126]
    • now back in sequence(1,-6,3) call. Our [-6]+sequence(0,-126,3) computation [-6]+[-126] or [-6, -126], which is what we return
  • now back in sequence(2, 2, 3) call. Our [2]+sequence(1,-6,3) computation is therefore [2]+[-6,-126] or [2,6,-126]. Which is our final answer

Note that no redundant computation is done here. And it stays as close as possible from your initial answer.

Another, more "functional" recursion, which for the record, was my previous main answer (what is now my main answer was 1st provided as an alternative solution, before I realized it was probably the one your are expected to provide)

def sequence(N, x0, r):
    if N == 0:
        return [x0]
    else:
        prev=sequence(N-1, x0, r)
        prev.append(r * prev[-1] * (1-prev[-1]))
        return prev

It is also recursive, and efficient. But not as elegant. I mean, the recursion here is just a way to repeat N times the prev.append(...) line. We could have achieved the same result by iterating N times that line with a for loop. So recursion brings nothing. Whereas in the first solution, it has the advantage to stick to mathematical recurrent definition of the sequence (that is one advantage of recursion. It may be harder to understand for computer scientist used to imperative programming. But for a mathematician, it is closer to the way we define sequences)

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

Looks like you might want

def compute_value(N, x0, r):
    if N == 0:
        return x0
    x_n = compute_value(N - 1, x0, r)
    return r * x_n * (1 - x_n)


sequence = [compute_value(n, 2, 2) for n in range(10)]

print(sequence)

This prints out

[2, -4, -40, -3280, -21523360, -926510094425920, -1716841910146256242328924544640, -5895092288869291585760436430706259332839105796137920554548480, -69504226188572366382469893394830651557109425404264568995802412215018036314883217970500884577054804760905832770274449717760, -9661674916144457552727034361009790527700732880801664275092268814451233373207768500008969714893014677195041164647293059752576754550666470442049020239364319771280275066863699741389031161203686169060521699834121138295895752329492941497636218270720]

(boy, those are some big negative numbers...)

Improve this answer

11 Comments

This is quite inefficient.
@BlackBeans Yes. It can be made efficient by adding the @cache decorator to compute_value. ;-)
Yes. That is the logistic sequence. It is supposed to be used with initial values between [0,1]. It has a fascinating behavious, depending on value of r. If r<1, it converges toward 0. If 1<r<3 it converges but not toward 0. If 3<r<3.56 it doesn't converge strictly speaking, but oscillate between 2, 4, 8, ... limits. Over 3.56, it is pure chaos. And in complex space, the area of r for which the sequence is chaotic is (ignoring a simple geometric transformation) Mandelbrot's fractal.
Oh, and also, it is a simple modelisation of a pandemic evolution, r, being the same "R" parameter we always hear about in pandemic talk.
@user996159 literally add @cache before compute_value, after importing it from functools (ie. from functools import cache).
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.