Recursive Fibonacci algorithm with variant

Question

I've implemented a traditional fibonacci recursion related with the reproduction of a population of rabbits in python2.7

def fibonacci(n):
    if n is 0 or n is 1: return 1
    else: return (fibonacci(n-1)+fibonacci(n-2))

This code computes the population if exactly one month after two rabbits mate, they produce one male and one female rabbit. Now I need to modify the code to compute the population if every pair of reproduction-age rabbits produces a litter of k rabbit pairs (instead of only 1 pair). How can I do this in a recursive way? What is the most appropriate model for the recursive case?

What is the mathematical recurrence relation? Is it f(0) = f(1) = k, and f(n+2) = ((n+2)choose k) * (f(n+1) + f(n))? — inspectorG4dget
– inspectorG4dget, Commented Aug 4, 2014 at 2:49

mleyfman · Accepted Answer · 2014-08-06 06:15:47Z

3

Well let's try and derive the sequence, which is also known as a multi-nacci sequence of order k. See this paper for some more interesting tidbits.

The basic rule is the same: it takes 1 month to for a pair to mature

Therefore at:

Month 0: 1 pair exists (young)

Month 1: 1 pair exists (adult)

Month 2: 1 pair exists (adult) + k pairs exist (young) = 1 + k total

Month 3: 1 + k pairs exist (adult) + k pairs exist (young) = 1 + 2k total

Month 4: 1 + 2k pairs exist (adult) + k (1 + k) pairs exist (young) = 1 + k(3 + k) total

Month 5: 1 + 3k + k^2 pairs exist (adult) + k (1 + 2k) pairs exist (young) = 1 + k(4 + 3k) total

and so on...

Notice that with each month, the total number of rabbit pairs is k * number of adults (which are two generations old) + number of young pairs (which are 1 generation old). Therefore the amount of rabbits at generation n is k * number of rabbits at generation n - 2 (as these are now all adults) + number of rabbits at generation n - 1

Mathematically: f(0) = 1, f(1) = 1, f(n) = f(n-1) + k * f(n-2).

Code:

def fibnum(n, k):
    if n < 0:
         raise ValueError("n must be a positive value")
    if n is 0 or n is 1:
        return 1
    else: 
        return (fibnum(n-1, k) + k * fibnum(n-2, k))

Notes:

This code is 0-based: so 5th month is n=4 and so on.
WARNING: this sequence grows ridiculously fast with larger k (so calculating fibnum(100, 100) may take a while). Memoization is advised to provide a significant speedup for increasing n.

Update: Changed code to accept k as a parameter, and cleaned up my code formatting a bit. Added reference to multinacci sequence

edited Aug 6, 2014 at 6:15

answered Aug 4, 2014 at 3:15

mleyfman

6334 silver badges13 bronze badges

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

5 Comments

Juan David Over a year ago

Is not working, k-fibNum with n=5 and k=3 must return 19 but your implementation is returning 40

Juan David Over a year ago

def fibonacci(n,k): if n is 0 or n is 1: return 1 else: return fibonacci(n-1,k) + k*fibonacci(n-2,k)

mleyfman Over a year ago

You have an off by 1 error. I have my months 0-based, while you use 1-based. My function with n=4 and k=3 does return 19. I will modify my function to accept k as a parameter instead of having it defined externally.

Juan David Over a year ago

But Im you using the same if statement used by k-fibnum. BTW your mathematical argument is excellent, congrats

mleyfman Over a year ago

By "you have an off by 1 error" I don't mean the code is wrong, I'm saying that your interpretation of the results is wrong. N=5 and k=3 should return 40 in my case, as it refers to the 6th month, while the value of 19 refers to the 5th month (or n=4).

Collectives™ on Stack Overflow

Recursive Fibonacci algorithm with variant

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related