Recursive Relationship - Fibonacci

0
votes

I've been doing some past papers for my ComSci course and I've ran into a bit of trouble understanding this question:

"Define a recursive relationship that expresses the number of calls involved in using the below function to find the nth Fibonacci number.: "

def f(n):
if n == 1 or n == 2:
    return 1
else:
    return f(n - 1) + f(n - 2)

I understand how the function works f(1), f(2) requires 1 call f(3) requires 3, f(4) requires 5 etc... However, I'm at a loss as to how to approach this question.

Thanks for reading :)

1
mathrecursionfibonacci
Does "Define a recursive relationship" mean "write a function" or "write an essay"? - Aaron Brager
The nice thing is that the number of calls required is the fibonacci sequence again. Think about it. - Guntram Blohm
I think it's asking for some mathematical answer. I.e. work out nth calls for f(n) f(n-1) f(n-2). That's my current understanding anyhow. I noticed that the number of calls required for f(n) is the sum of the previous number of calls required for (n-1) + (n-2) + 1. Am I sort of on the right lines? - Toby
You are exactly on the right line. You just need to formalize your answer a little - you can see my answer below if you need help doing that. - Steven Hansen
@Guntram Nice observation. - Steven Hansen

1 Answers

1
votes

The question asks you to explain how many calls will be made to f based on n. The part that says, "Define a recursive relationship" is actually a hint about your answer.

So your answer will look something like:

Let T(x) be the function which defines the number of calls to compute f(x)

Then:

T(n) = { something using T and values less than n }

If you are trying to figure this out yourself - stop here, Spoilers follow (so your question is answered completely).

----------------------------------  Spoiler -------------------------------





n=1: T(1) = 1
n=2: T(2) = 1
n>2: T(n) = 1 + T(n - 1) + T(n - 2) 





--------------------------------- End Spoiler ------------------------------