This course will teach participants about installing and configuring Python, syntax, importing, statements, types, strings, booleans, files, lists, tuples, comprehensions, functions, and classes.

```
def fib(x):
"""assumes x an int >= 0
Returns Fibonacci of x"""
assert type(x) == int and x >= 0,'wrong'
if x == 0 or x == 1:
return 1
else:
returnfib12=(fib(x-1) + fib(x-2))
return returnfib12
def testFib(n):
for i in range(n+1):
print ('fib of', i, '=', fib(i))
fib0=fib(0)
fib1=fib(1)
fib2=fib(2)
fib3=fib(3)
fib4=fib(4)
fib5=fib(5)
fib6=fib(6)
fib7=fib(7)
fib8=fib(8)
fib9=fib(9)
```

I modified code so I can see variables in debugger ide

returnfib12=(fib(x-1) + fib(x-2))

keeps on calling fib(x) function until finished

but there is no for or while loop

what is decrementing

returnfib12

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

To add to what aikimark says, you might see this termed and "exit condition". Without such a condition, your recursion will recur infinitely right up until the stack overflows. Any time you write a recursive function you have to make sure that an exit condition is present. The exit condition ensures that your recursion has a way to terminate.

Now, your exit condition is what aikimark referenced in his snippet. So how does it become true? Well, each time you call the recursive function, you are passing one less (and two less) than the current value. In other words, each time you call it (within itself), you are decrementing the value. At some point you will be passing in 1 as the value, at which point your exit condition will be met. At this point, each nested call returns to the outer call, all the way back up the call stack to the very first invocation of your function--i.e. the one that was called from outside this function.

You should really think in terms of the definition: "if x is 0 or 1, the result is 1. Otherwise the result is f(x-1) plus f(x-2)". It may be difficult to accept at first, but it is that way :)

A side note: Computing Fibonacci (or factorial or the like functions) recursively is extremely inefficient from computation point of view. Think only about fib(5) where the result is fib(4) + fib(3). Now fib(4) also calculates fib(3). And because one step calls the function twice (not considering the final steps), then the number of calculation is roughly like 2 ^ n where n is the argument of the most outer fib(). For fib(10), you can think about 1000 calculations. For fib(20), there is about 1 000 000 calculation.

Well, actually the number of steps may be very reduced by the final condition. Anyway, try the following modified example:

```
#!python3
steps = 0
def fib(x):
global steps
steps += 1
if x == 0 or x == 1:
return 1
else:
return fib(x-1) + fib(x-2)
for n in range(31):
steps = 0 # must be set this way, because it is global for the fib()
print('fib({}) = {} ({} steps)'.format(n, fib(n), steps))
```

The global variable ```
fib(0) = 1 (1 steps)
fib(1) = 1 (1 steps)
fib(2) = 2 (3 steps)
fib(3) = 3 (5 steps)
fib(4) = 5 (9 steps)
fib(5) = 8 (15 steps)
fib(6) = 13 (25 steps)
fib(7) = 21 (41 steps)
fib(8) = 34 (67 steps)
fib(9) = 55 (109 steps)
fib(10) = 89 (177 steps)
fib(11) = 144 (287 steps)
fib(12) = 233 (465 steps)
fib(13) = 377 (753 steps)
fib(14) = 610 (1219 steps)
fib(15) = 987 (1973 steps)
fib(16) = 1597 (3193 steps)
fib(17) = 2584 (5167 steps)
fib(18) = 4181 (8361 steps)
fib(19) = 6765 (13529 steps)
fib(20) = 10946 (21891 steps)
fib(21) = 17711 (35421 steps)
fib(22) = 28657 (57313 steps)
fib(23) = 46368 (92735 steps)
fib(24) = 75025 (150049 steps)
fib(25) = 121393 (242785 steps)
fib(26) = 196418 (392835 steps)
fib(27) = 317811 (635621 steps)
fib(28) = 514229 (1028457 steps)
fib(29) = 832040 (1664079 steps)
fib(30) = 1346269 (2692537 steps)
```

That is almost 2 million calls for just 29, and about another one million of calculations for just one more. The recursive nesting also means eating the computer memory. And you will definitely observe it takes more and more time to compute. The alternative non-recursive solution (using a loop and more variables) needs about that many of loops how big is the argument -- very fast and no memory overhead when compared with the recursive solution.Recursive solutions may be very powerful when you have to tackle with problems formulated the way you think in mathematics/logic. But one have to be careful in cases like Fibonacci.

so any

return a-1 is recurisive because of the minus -1

Does recursive happen in

fib

testfib

or both

return a-1 is recurisive because of the minus -1

Does recursive happen in

fib

testfib

or both

so anyNo, any function that calls itself is recursive. The minus 1 is something that is kind of a helper to get to your exit condition.

return a-1 is recurisive because of the minus -1

Think about it like this:

Imagine that execution begins at the top. Notice how inside of

So, how does the exit condition come into play? Examine:

Imagine that the green arrows represent inputs into successive calls, and the purple arrows represent return values.Trace each green line until you cannot go any deeper. Then follow the purple line back up, but only one level. Once you follow a purple, go down the second green line until you cannot go any deeper. Follow the purple up one level. Now add the two values you got from the two purple lines. Then pass this value back up one level. Then go to the next green line. You repeat this process until you get to the thick purple arrow at the top. This is the output of your whole recursive chain of calls. The exit condition is encountered at any point in the picture where you do not have a green arrow to follow, at which point you must follow a purple arrow.

in your first two cases (0 and 1), the function will return a 1 value because of this statement:

Try next case your self

Why is x incrementing?

http://filedb.experts-exchange.com/incoming/2014/08_w32/864334/Untitled.png

is this

fib3=fib(3)

As an experiment to understand recursion, try the following simpler recursive function:

```
#!python3
def fn():
print('.', end='', flush=True)
fn()
if __name__ == '__main__':
fn()
```

You have to be fast to see the beginning of the output:
```
c:\_Python\rgb192\Q_28489785>a.py
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
................................................................................
...................................Traceback (most recent call last):
File "C:\_Python\rgb192\Q_28489785\a.py", line 7, in <module>
fn()
File "C:\_Python\rgb192\Q_28489785\a.py", line 4, in fn
fn()
File "C:\_Python\rgb192\Q_28489785\a.py", line 4, in fn
fn()
[...snip...]
File "C:\_Python\rgb192\Q_28489785\a.py", line 4, in fn
fn()
File "C:\_Python\rgb192\Q_28489785\a.py", line 3, in fn
print('.', end='', flush=True)
RuntimeError: maximum recursion depth exceeded
```

The dotted lines is actually a single line wrapped in console. You are a kind of lucky, because Python allows only limited recursion depth (1000, could be set). Otherwise, the recursion would be infinite (actually until consuming all available memory). The extra arguments in the This should help you to understand why a condition must be tested before the function is called recursively. Let's reformulate that example: "Printing n dots means... If there is anything to print (i.e. n >= 1) then print one dot and then print the tail of n-1 dots using the same rule."

```
#!python3
def fn(n):
if n >= 1:
print('.', end='', flush=True)
fn(n-1)
if __name__ == '__main__':
fn(10)
```

Now, for your questions, the n is always decremented only. The dots are added one after another. The two phenomena are kind of unrelated.
this error is in python 3

```
#!python3
def fn():
print('.', end='', flush=True)
fn()
if __name__ == '__main__':
fn()
```

Message File Name Line Position

Traceback

<module> C:\Users\Acer\Documents\po

fn C:\Users\Acer\Documents\po

TypeError: 'flush' is an invalid keyword argument for this function

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Python

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

fib(x-1)and

fib(x-2)============

in your first two cases (0 and 1), the function will return a 1 value because of this statement:

Open in new window

For your next case (2), the fib function will be invoked twice with a value of 1 and 0 (see above), which both return 1 values, which are added and the sum (2) is returned.

For your next case (3), the fib function is invoked twice with the value of 2 and 1. We see what happens when 2 is passed and when 1 is passed, so we add 2 and 1 and return 3.

try the next case (4) for yourself.