Recursion function in Python

Question

Consider this basic recursion in Python:

def fibonacci(number):
    if number == 0: return 0
    elif number == 1:
        return 1
    else:
        return fibonacci(number-1) + fibonacci(number-2)

Which makes sense according to the (n-1) + (n-2) function of the Fibonacci series.

How does Python execute recursion that contains another recursion not within but inside the same code line? Does the 'finobacci(number-1)' complete all the recursion until it reaches '1' and then it does the same with 'fibonacci(number-2)' and add them?

For comparison, the following recursive function for raising a number 'x' into power 'y', I can understand the recursion, def power calling itself until y==0 , since there's only one recursive call in a single line. Still shouldn't all results be '1' since the last command executed is 'return 1' when y==0, therefore x is not returned?

def power(x, y):
    if y == 0:
        return 1
    else:
        return x*power(x, y-1)

score 17 · Answer 1 · edited Jun 20 '20 at 09:12

Short Answer

Each time Python "sees" fibonacci() it makes another function call and doesn't progress further until it has finished that function call.

Example

So let's say it's evaluating fibonacci(4).

Once it gets to the line return fibonacci(number-1) + fibonacci(number-2), it "sees" the call fibonacci(number-1).

So now it runs fibonacci(3) - it hasn't seen fibonacci(number-2) at all yet. To run fibonacci(3), it must figure out fibonacci(2)+fibonacci(1). Again, it runs the first function it sees, which this time is fibonacci(2).

Now it finally hits a base case when fibonacci(2) is run. It evaluates fibonacci(1), which returns 1, then, for the first time, it can continue to the + fibonacci(number-2) part of a fibonacci() call. fibonacci(0) returns 0, which then lets fibonacci(2) return 1.

Now that fibonacci(3) has gotten the value returned from fibonacci(2), it can progress to evaluating fibonacci(number-2) (fibonacci(1)).

This process continues until everything has been evaluated and fibonacci(4) can return 3.

To see how the whole evaluation goes, follow the arrows in this diagram:

Enter image description here

The visualization helps a lot to understand it very quickly even without reading the text. Thanks for the work. — colidyre, Nov 24 '15 at 10:36

score 10 · Accepted Answer · answered Dec 04 '12 at 17:38

10

In the expression fibonacci(number-1) + fibonacci(number-2) the first function call will have to complete before the second function call is invoked.

So, the whole recursion stack for the first call has to be complete before the second call is started.

answered Dec 04 '12 at 17:38

Martijn Pieters

1,048,767
296
4,058
3,343

score 5 · Answer 3 · answered Dec 04 '12 at 17:41

does the 'finobacci(number-1)' completes all the recursion until it reaches '1' and then it does the same with 'fibonacci(number-2)' and add them?

Yes, that's exactly right. In other words, the following

return fibonacci(number-1) + fibonacci(number-2)

is equivalent to

f1 = fibonacci(number-1)
f2 = fibonacci(number-2)
return f1 + f2

score 3 · Answer 4 · edited Sep 17 '16 at 15:58

3

You can use the rcviz module to visualize recursions by simply adding a decorator to your recursive function.

Here's the visualization for your code above:

Output of OP's function with rcviz

The edges are numbered by the order in which they were traversed by the execution. The edges fade from black to grey to indicate order of traversal: black edges first, grey edges last.

(I wrote the rcviz module on GitHub.)

edited Sep 17 '16 at 15:58

Peter Mortensen

30,738
21
105
131

answered Apr 28 '14 at 22:51

carlsborg

2,628
19
21

score 2 · Answer 5 · edited Sep 17 '16 at 15:56

2

I would really recommend that you put your code in the Python tutor.

You will the be able to get it on the fly. See the stackframe, references, etc.

edited Sep 17 '16 at 15:56

Peter Mortensen

30,738
21
105
131

answered Dec 04 '12 at 17:43

jassinm

7,323
3
33
42

score 0 · Answer 6 · edited Sep 17 '16 at 15:55

0

Your second recursion functions does this (example), so 1 will not be returned.

power(2, 3)

2 * power(2, 2)

2 * 2 * power(1,2)

2 * 2 * 2 * power(0,2) # Reaching base case

2 * 2 * 2 * 1

8

edited Sep 17 '16 at 15:55

Peter Mortensen

30,738
21
105
131

answered Dec 04 '12 at 17:43

Akavall

82,592
51
207
251

score 0 · Answer 7 · answered Dec 04 '12 at 17:43

You can figure this out yourself, by putting a print function in the function, and adding a depth so we can print it out prettier:

def fibonacci(number, depth = 0):
    print " " * depth, number
    if number == 0:
        return 0
    elif number == 1:
        return 1
    else:
        return fibonacci(number-1, depth + 1) + fibonacci(number-2, depth + 1)

Calling fibonacci(5) gives us:

We can see that 5 calls 4, which goes to completion, and then it calls 3, which then goes to completion.

score 0 · Answer 8 · answered Dec 04 '12 at 17:44

Matthew and MArtjin are right but I thought I might elaborate:

Python does stuff from left to right whenever it can. Exceptions to this rule are implied by brackets.

in x*power(x, y-1): x is evaluated then power is evaluated

While in fibonacci(number-1) + fibonacci(number-2), fibonacci(number-1) is evaluated (recursively, til it stops) and then fibonacci(number-1) is evaluated

score 0 · Answer 9 · answered Apr 20 '20 at 18:40

0

  def fib(x):
    if x == 0 or x == 1:
    return 1
  else:
    return fib(x-1) + fib(x-2)

print(fib(4))

answered Apr 20 '20 at 18:40

DimiDak

4,820
2
26
32

score -1 · Answer 10 · edited Jan 07 '18 at 07:35

-1

def fib(n):
  if n <= 1:
  return n
else :
  return fib(n - 1) + fib(n - 2)

edited Jan 07 '18 at 07:35

Pedram

15,766
10
44
73

answered Jan 07 '18 at 05:07

Seetha Lakshmi

1
1

Recursion function in Python

10 Answers10

Short Answer

Example

Linked