In their most recent webinar, Skyport Systems explores ways to isolate and protect critical databases to keep the core of your company safe from harm.
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)
if x == 0 or x == 1:
#!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 steps breaks the nesting rules -- it is not created as another local variable. This way, it can count the steps done on different levels of nesting. When runnig the code, you get the output:
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.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
in your first two cases (0 and 1), the function will return a 1 value because of this statement:
Try next case your self
#!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 print cause printing the next dot just after the previous (no output of the end of the line), and to display the dot on the console as soon as possible (the flush=True, i.e. not waiting until the end of line).#!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.
#!python3
def fn():
print('.', end='', flush=True)
fn()
if __name__ == '__main__':
fn()
If you are experiencing a similar issue, please ask a related question
Join the community of 500,000 technology professionals and ask your questions.