1

I want to create a function that makes a so called super Fibonacci sequence which is a list of numbers, that from the third term onwards, every term is the sum of all the previous terms. It takes 2 arguments: t2 and n. t2 is the second term in the list and n is the number of terms in the list. For example.

superFibSeq(10,10) >>> [1,10,11,22,44,88,176,352,704,1408]
superFibSeq(4,10) >>> [1, 4, 5, 10, 20, 40, 80, 160, 320, 640]

I've been stuck on this for a bit with no idea where to start. How should I think about this if I want to use only recursion.

giddo244
  • 33
  • 3
  • Assume I have already calculated `superFibSeq(t2, n-1)` and I give the result to you. How would you use that to calculate `superFibSeq(t2, n)`? – Stef Nov 04 '20 at 12:34

2 Answers2

0

Someone above gave negative points for saying recurion in this problem is really strange. You want recursion, sure.

def f(t2, n):
    if n == 0:
       return []
    elif n == 1:
       return [1]
    elif n == 2:
        return [1, t2]
    else:
        temp = f(t2, n - 1)
        return temp + [sum(temp)]

This algorithm is O(n^2) rather than O(n)

Frank Yellin
  • 6,522
  • 1
  • 9
  • 20
  • To calculate f(n), I have to first calculate f(n-1), and then sum up n-1 integers. So the time to calculate f(n) is 1 + 2 + .... n-1 = O(n^2). I give up. What didn't you like about this algorithm. It precisely answered the question. – Frank Yellin Nov 04 '20 at 21:43
  • The OP thinks of an interesting problem to practice recursion. They get stuck and ask for help. You're handing them a snippet of code that solves the problem. I don't think that's helpful. – Stef Nov 04 '20 at 21:48
  • 1
    You seem to think the only purpose of SO is to literally answer the user's question. I've discovered that oftentimes, especially with new posters, you need to let them know that they're asking the wrong question. I don't know whether the OP noticed that the terms just doubled after the third, but I'd consider it a dereliction of duty to not point that out, and to let the original poster know that in real life, this is a bad use of recursion. I'm sorry you seem to disagree. – Frank Yellin Nov 04 '20 at 21:59
  • Thanks for the insight! I understand that this was quite a bad question if comparing O(n^2) vs O(n). This was a question from a problem set and I had no idea where to start. – giddo244 Nov 05 '20 at 11:46
-2

It sounds like recursion is a really strange idea for this program.

Your terms are:

1, t2, (1 + t2), 2(1 + t2), 4(1 + t2), 8(1 + t2), .... 2**(n-2)(1 + t2)
Frank Yellin
  • 6,522
  • 1
  • 9
  • 20
  • You found a formula, and that is great, but that's not a reason to call "really strange idea" anything that does not use your formula. – Stef Nov 04 '20 at 12:36
  • Using recursion to solve a problem that doesn't even require iteration is strange. – Frank Yellin Nov 04 '20 at 18:23