Python recursive functions

[Ayman_2001]

Greetings,
I've been doing this course on Udacity called CS101 it's quite a effective and challenging one and so far i've enjoyed it quite a lot. But recursive functions are coming that easy to me as I find it somewhat confusing.Thus, if someone can elaborately explain me this function, it would be extremely helpful to me. Thank you!

# Function for nth Fibonacci number

def Fibonacci(n):
	if n<0:
		print("Incorrect input")
	# First Fibonacci number is 0
	elif n==0:
		return 0
	# Second Fibonacci number is 1
	elif n==1:
		return 1
	else:
		return Fibonacci(n-1)+Fibonacci(n-2)


# Driver Program

print(Fibonacci(5))

#This code is contributed by Saket Modi

How does it loop without any looping statements?

[ndc85430]

Remember that each time a function is called, a new frame is created on the stack where the variables local to the function exist. ForSo each time the function calls itself recursively, a new stack frame is created with the value of n that was passed. For the non-recursive call (that is, the base case), the return value is placed on the stack, the stack frame cleaned up and then the calling function takes the return value and progresses. In the recursive case, the stack will keep growing (with each frame having a smaller value of n), until the base case is reached. IIRC, the book "Grokking Algorithms" has nice diagrams to explain this.

[jefsummers]

Answering the question at the bottom first, it "loops" by calling itself in the return line. Which is not exactly a loop, but I understand the question.

This one is challenging because the return line calls Fibonacci twice (and therefore not really a good example). Stick a print statement at line 2, something like

print(f'n is {n}')

You will see that it winds down the first argument in the return before moving to the second. Not sure it really does what is planned, as it gives a single value and Fibonacci is typically a sequence, so don't count on this giving a right answer. Rather it demonstrates recursion.
I suggest adding that print statement, then removing the +Fibonacci(n-2) from the return line. Run it, see the results, and you will understand recursion better.

[Ayman_2001]

In the last line:

return Fibonacci(n-1) + Fibonacci (n-2) 

if the input is 5 shouldn't the output be Fibonacci(5-1) + Fibonacci(5-2) = 7? how come the answer comes out to be 5 and it's correct??

[deanhystad]

I do not like this demonstration of recursion and it I think the only reason Fibonacci is used is because it is so much easier and more efficient when solved without using recursion.

How do you calculate Fibonacci numbers? The next number in the sequence is equal to the sum of the previous two numbers.

0, 1, (0 + 1), (1 + (0 + 1)), ((0 + 1) + (1 + (0 + 1)))

Using a list this is quite easy to do;

fibonacci = [0, 1]
while len(fibonacci) < 10:
    fibonacci.append(fibonacci[-2] + fibonacci[-1])

print(fibonacci)

Output:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

But what how can you calculate the next number in the Fibonacci sequence if you don't have the list of previous numbers? You have to generate the list, and that is what the recursion is doing in your example. Let's expand Fibonacci(5):

def Fibonacci(n):
    if n<0:
        print("Incorrect input")
    # First Fibonacci number is 0
    elif n==0:
        return 0
    # Second Fibonacci number is 1
    elif n==1:
        return 1
    else:
        return Fibonacci(n-1)+Fibonacci(n-2)

Fibonacci(5) = Fibonacci(4) + Fibonacci(3)
             = (Fibonacci(3) + Fibonacci(2)) + Fibonacci(3)
             = (Fibonacci(3) + (Fibonacci(1) + Fibonacci(0))) + Fibonacci(3)
             = (Fibonacci(3) + (1 + 0)) + Fibonacci(3)
             = (Fibonacci(3) + 1) + Fibonacci(3)
             = ((Fibonacci(2) + Fibonacci(1)) + 1) + Fibonacci(3)
             = ((Fibonacci(2) + 1) + 1) + Fibonacci(3)
             = (((Fibonacci(1) + Fibonacci(0)) + 1) + 1) + Fibonacci(3)
             = (((1 + 0) + 1) + 1) + Fibonacci(3)
             = (3) + (Fibonacci(2) + Fibonacci(1))
             = (3) + (Fibonacci(2) + 1)
             = (3) + ((Fibonacci(1) + Fibonacci(0)) + 1)
             = (3) + ((1 + 0) + 1)
             = (3) + (2)
             = 5

Hopefully this provides a better view of what the recursion is doing. If the input is 1 or 0, the result can be calculated immediately. If the input is greater than 1, the value is calculated by calling the function again using n-1 and n-2. To calculate Fibonacci(5) we need to calculate Fibonacci(4) and Fibonacci(3). To calculate Fibonacci(3) we need to calculate Fibonacci(2) and Fibonacci(1). To calculate Fibonacci(2) we need to calculate Fibonacci(1) and Fibonacci(0). Fibonacci(1) and Fibonacci(0) can be calculated directly.

Maybe it is easier to think of the problem like this:

def Fibonacci2():
    return 1 + 0

def Fibonacci3():
    return Fibonacci2() + 1

def Fibonacci4():
    return Fibonacci3() + Fibonacci2()

def Fibonacci5():
    return Fibonacci4() + Fibonacci3()

print(Fibonacci5())

Here the recursion is replaced by giving each number it's own function. Though it looks slightly different, what it does is the same. The only difference is the recursive solution uses the same Fibonacci(N) in place of FibonacciN.

Not all languages support recursion, though nearly all modern programming languages do. FORTRAN and COBOL are two historically important languages that use statically allocated variables instead of a stack. These languages cannot call a function recursively because there is no place to store the intermediate results.

[jefsummers]

Another example of recursion:
Print the series of squares of a number repeatedly until the number is over 10,000, greatest to smallest.

def recurse(number):
    if number < 10000 :
        recurse(number*number)
    print(number)
    return

recurse(2)

Output:
65536
256
16
4
2

Best non-contrived example of recursion I can think of is Towers of Hanoi.

[ndc85430]

Computing n! is also a natural example, since the maths is recursive by definition!