recursive function paradox in Python.. how can it be explained?

Question

I made a very simple function that takes a list of numbers and returns a list of numbers rounded by some digits:

def rounded(lista, digits = 3):
    neulist = []
    for i in lista:
        neulist.append(round(i, digits))
    return neulist

However, I mistakenly put the function itself in the code instead of the built-in round() (as in the example below):

def rounded(lista, digits = 3):
    neulist = []
    for i in lista:
        neulist.append(rounded(i, digits))
    return neulist

and got this output:

Traceback (most recent call last):
  File "<pyshell#286>", line 1, in <module>
    rounded(a)
  File "<pyshell#284>", line 4, in rounded
    neulist.append(rounded(i, digits))
  File "<pyshell#284>", line 3, in rounded
    for i in lista:
TypeError: 'float' object is not iterable

The question is: how does the interpreter know that it had to apply the function rounded() while evaluating the function rounded() itself? How can it anyway now that rounded() is a function taking floats if it is attempting to interpret that very function? Is there a sort of two cycle procedure to evaluate & interpret functions? Or am I getting something wrong here?

off-topic, just as a side note: `rounded = lambda l: map(lambda x: round(x, 1), l)` — Pavel, May 13 '14 at 18:00

score 4 · Accepted Answer · answered May 13 '14 at 17:57

4

The function is an object. It is created at definition, not when it is called, so if Python didn't know how to use it, it would've raised an error before any calling was done.
However, you called it with a list. During the iteration, the function is called recursively with the first item of the list - presumably, a float. With this float as argument, for i in lista: doesn't make sense anymore, and you have the error.

answered May 13 '14 at 17:57

Roberto

2,696
18
31

2

To add some more to what I believe is the correct answer here: you called `rounded(a_list)`, which inside of the `for` loop, extracts the first item from that list, `i`, and calls `rounded(i, digits)`. Since `i` is a float, you'll run into an error when in the second `rounded` call, you try to do a `for (new_i) in i`. – huu May 13 '14 at 18:02
you are right, the error was prompted when I called the function and now when I instantiated it, so I guess that was just my illusion. Thanks for the quick and clear answer! – DaniPaniz May 13 '14 at 18:04

score 0 · Answer 2 · answered May 13 '14 at 18:01

You've just stumbled upon recursion.

Recursive functions are very common in programming. Consider the following (naive) function for calculating the nth fibbonacci number:

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

The function knows that it calls itself, because the function definition is noted as soon as the interpreter reaches fib(x):. From that point on, fib is defined. For python in particular, since it's a dynamically typed language, there's no difference if you call the function with a integer, a string or a float - all it matters is that the function takes exactly one argument.

score 0 · Answer 3 · answered May 13 '14 at 18:07

There are indeed two processes occurring here. The function is compiled as it's encountered in the source text, then a call is made to it afterward. The body of the function includes a call to rounded, but that's actually kept track of as the name of the function. Check this out:

def fun1(x):
    if x == 0:
        print x
    else:
        fun1(x-1)

fun2 = fun1

def fun1(x):
    print x

fun2(3)

Here we're defining fun1() with an apparently recursive call to itself. However, after redefining fun1(), the call in the first definition of the function now refers to a different function entirely.

recursive function paradox in Python.. how can it be explained?

3 Answers3