[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

recursive calling function

Posted on 2014-08-03
14
Medium Priority
?
345 Views
Last Modified: 2014-08-04
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)

Open in new window


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
0
Comment
Question by:rgb192
  • 4
  • 4
  • 3
  • +1
14 Comments
 
LVL 46

Expert Comment

by:aikimark
ID: 40238229
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:
if x == 0 or x == 1:

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.
0
 
LVL 75

Expert Comment

by:käµfm³d 👽
ID: 40238269
*No Points*

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.
0
 
LVL 29

Expert Comment

by:pepr
ID: 40238387
To add what aikimark and kaufmed wrote, when constructing any recursive function, you should think the way that follows them mathematical definition. You may not be used to think that way when programming other things, because you usually think in terms of steps at the same level of nesting. However, when calling a function recursively, the inner local variable (here x) is different from the outer local variable. In mathematics, you would wrote x' = x - 1. Here is where the decrementing is done. The x - 1 is evaluated and the result is passed to the inner x.

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))

Open in new window

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)

Open in new window

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.
0
Important Lessons on Recovering from Petya

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.

 

Author Comment

by:rgb192
ID: 40239511
so any
return a-1 is recurisive because of the minus -1

Does recursive happen in
fib
testfib

or both
0
 
LVL 46

Assisted Solution

by:aikimark
aikimark earned 668 total points
ID: 40239536
You are kicking of the process in the testfib function.  That passes the initial value.  Thereafter, the fib function calls itself until it gets down to a 1 or 0 input.
0
 
LVL 75

Assisted Solution

by:käµfm³d 👽
käµfm³d   👽 earned 664 total points
ID: 40239811
so any
return a-1 is recurisive because of the minus -1
No, any function that calls itself is recursive. The minus 1 is something that is kind of a helper to get to your exit condition.

Think about it like this:

Screenshot
Imagine that execution begins at the top. Notice how inside of fib we have two calls to fib itself? Let's pretend that the first call takes the path visible on the left side of the image, and the second call takes the right side. You'll see at the second level there are two calls. Each of these two call itself has two calls to fib. As such, we create another branching. Even at level 3, each call to fib potentially has two calls to fib. Why "potentially?" You have potential calls to fib because of the exit condition I mentioned above. Once the exit condition is reached, we basically start erasing levels from the image from the bottom up. In execution of the code that equates to values being returned to each caller (i.e. each level above).

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

Flow
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.
0
 
LVL 29

Expert Comment

by:pepr
ID: 40239902
@kaufmed: Nice pictures. And the face :)
0
 

Author Comment

by:rgb192
ID: 40239939
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)
0
 
LVL 75

Expert Comment

by:käµfm³d 👽
ID: 40239948
Yes, that picture is fib(3). It was going to be a chore trying to lay that graphic out for anything greater than 3  = )
0
 
LVL 46

Expert Comment

by:aikimark
ID: 40239949
It isn't the case that x is incrementing.  You are getting values returned from functions that are added to other function results, but the value of x should never increase once you make the call to the fib function.
0
 
LVL 29

Expert Comment

by:pepr
ID: 40240030
When having difficulty to understand the recursion on the kaufmed pictures, just think as if the code in one rectangle was a code outside the fib definition. Just obscure the def fib(x): line. Think in terms that the code is outside of fib definition but accidentally it uses exactly the same statements and constructs. Let it have nothing common with the called fib(x-1) + fib(x-2). The result of the two fib() calls are summed. Suddenly, you may now remember that the result is returned as the result of the function call at the higher lever. It is actually not that important (for one step) if the above function has the same name. It is not visible from inside. However, it is important (that it has the same name) if you want to see a big picture.

As an experiment to understand recursion, try the following simpler recursive function:
#!python3
def fn():
    print('.', end='', flush=True)
    fn()
    
if __name__ == '__main__':
    fn()

Open in new window

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

Open in new window

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).

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)

Open in new window

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

Author Comment

by:rgb192
ID: 40240089
I errored in both python 2 and python 3
this error is in python 3

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

Open in new window


Message      File Name      Line      Position      
Traceback                        
    <module>      C:\Users\Acer\Documents\portable-python\myfiles\recur.py      7            
    fn      C:\Users\Acer\Documents\portable-python\myfiles\recur.py      3            
TypeError: 'flush' is an invalid keyword argument for this function
0
 
LVL 29

Accepted Solution

by:
pepr earned 668 total points
ID: 40240095
I see. The flush was added in Python 3.3 (https://docs.python.org/3/library/functions.html#print). Just remove it. It only will not be that nice.
0
 

Author Closing Comment

by:rgb192
ID: 40240258
I liked Kaufmed pictures and the easy recursive simplified function the best to understand

thanks.
0

Featured Post

Prep for the ITIL® Foundation Certification Exam

December’s Course of the Month is now available! Enroll to learn ITIL® Foundation best practices for delivering IT services effectively and efficiently.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Installing Python 2.7.3 version on Windows operating system For installing Python first we need to download Python's latest version from URL" www.python.org " You can also get information on Python scripting language from the above mentioned we…
Article by: Swadhin
Introduction of Lists in Python: There are six built-in types of sequences. Lists and tuples are the most common one. In this article we will see how to use Lists in python and how we can utilize it while doing our own program. In general we can al…
Learn the basics of strings in Python: declaration, operations, indices, and slicing. Strings are declared with quotations; for example: s = "string": Strings are immutable.: Strings may be concatenated or multiplied using the addition and multiplic…
Learn the basics of modules and packages in Python. Every Python file is a module, ending in the suffix: .py: Modules are a collection of functions and variables.: Packages are a collection of modules.: Module functions and variables are accessed us…
Suggested Courses
Course of the Month17 days, 23 hours left to enroll

831 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question