Adding Counter to recursive Fibonacci program

Question

I'm working with a basic Python MIT free courseware and I have run into a wall with a recursion exercise. The original program takes an integer and provides its Fibonacci using recursion. The book provides the script for the program, but the subsequent exercise asks to input a way for the program to recognize how many times fib(2) is executed on its way to calculating fib(n). ``

Here is the code:

def fib(n):
    """Assumes n is int > 0
    Returns Fibonacci Number of n"""
    if n ==0 or n==1:
        return n        
    else:
        return fib(n-1) + fib(n-2)

def testfib(n):
    for i in range(n+1):
        print('fib of', i, 'is ', fib(i))

x=int(input('Enter a number: '))

print('Fibonacci of', x, 'is',fib(x))
print(testfib(x))

There is an answer given in another thread I'm trying to wrap my head around and wondering if someone could explain how, what seems like tuples, in the else portion are serving as variables names in the below code? reference: Trouble adding feature to recursive Fibonacci program

def fib(n):
    """Assumes n is int > 0
    Returns the nth Fibonacci number and number of times it was called"""
    if n == 0 or n == 1:
        return n, 0
    else:
        f1, count1 = fib(n-1)
        f2, count2 = fib(n-2)
        sum_counts = count1 + count2
        if n == 2:
            sum_counts = 1
        return f1 + f2, sum_counts


def testfib(n):
    for i in range(n+1):
        f, count = fib(i)
        print('fib of', i, 'is ', f, end="\t")
        print('count of fib(2) is ', count)

x = int(input('Enter a number: '))

print('Fibonacci of', x, 'is', fib(x)[0])
print(testfib(x))

Maybe you are confused about tuple unpacking. It is described in the Python docs here: docs.python.org/3/tutorial/… — BurningKarl
– BurningKarl, Commented Jun 23, 2020 at 22:31
The fib() function returns a sequence of two items — a tuple — and they can be assigned directly into two different variables: i.e. a, b = fib(x). Doing this is called "tuple unpacking". — martineau
– martineau, Commented Jun 23, 2020 at 23:03
@BurningKarl & martineau - Thank you both this answered my question and 7u5h4r's answer provide the clarity I needed. — Cookie Monster
– Cookie Monster, Commented Jun 24, 2020 at 21:32

7u5h4r · Accepted Answer · 2020-06-24 08:54:12Z

1

Explaining it by each line

f1, count1 = fib(n-1)

Here fib returns f1 + f2, sum_counts (See in the end) so f1 = f1 + f2 and count1 = sum_counts

f2, count2 = fib(n-2)

Here fib returns f1 + f2, sum_counts (See in the end) so f2 = f1 + f2 and count2 = sum_counts

return f1 + f2, sum_counts

fib method is returning 2 values f1 + f2, sum_counts here so we have to unpack 2 values with the tuple or 2 variables

In your code, we are unpacking values by 2 variables below is an example of unpacking it by a tuple

def test():
    return 1, 2, 3, 4, 5
my_list = test()
for val in my_list:
    print(val)

edited Jun 24, 2020 at 8:54

answered Jun 23, 2020 at 21:51

7u5h4r

4653 silver badges10 bronze badges

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

Collectives™ on Stack Overflow

Adding Counter to recursive Fibonacci program

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related