Recursion effects in Python?

[Harshali_1]

Hello everyone,
I am a learner, who found this helpful community where one's query is satisfied in so many great ways.
I have one such query regarding Recursion. Can anyone help me to know about the effects of Recursion in Python? Does it cause any trouble?

[Reverend Jim]

That question is too vague to be answered in detail. There are problems for which recursion is appropriate and problems for which it is not. For example, traveresing a binary tree - appropriate. Calculating factorials of large numbers - not appropriate. Assuming bug-free code, the trouble is generally that of excessive stack space when the recursion is nested too deeply. Sometimes this can be mitigated by minimizing what goes onto the stack (minimizing the parameter list).

[Schol-R-LEA]

This rather old post of mine discusses the use of recursion in general terms; the discussion following it in that thread might prove of value as well. While it is presented vis a vis C++, it applies to Python just as well, IMAO.

[HimaniBansal]

Followings are caused by Recursion in Python:

• It can lead to consuming more time for calling a Function.
• Needs more function calls.
• Each function call stores a state variable to the program stack- consumes memory, can cause memory overflow.

[vegaseat]

Recursive functions have a neat look, but consume much stack space, Python sets a recursion limit of 1000. Recursive functions are rather slow, a while/for loop is much faster.

Here are some typical examples:

def get_factorial1(n):
    '''
    would be poor choice because of the many function calls
    each call has stack overhead, a while/for loop is much faster
    '''
    # base case, also exit condition
    if n <= 1:
        return 1
    # recursive case (return is needed)
    return n * get_factorial1(n - 1

def get_factorial3(n):
    '''
    avoids recursion and uses a faster for loop
    a factorial is 1*2*3*4*5*6*7* ...
    '''
    # base case 0! = 1 and 1! = 1
    if n <= 1:
        return 1
    factorial = 1
    for x in range(1, n+1):
        factorial *= x
    return factorial

[JamesCherrill]

Indeed there are cases where a loop can be used instead of recursion, and in those cases the loop will carry less overhead. These are mainly encountered in programming courses when the concept of recursion is first introduced.
(I don't know about Python specifically, but a decent compiler will recognise a tail recursion and optimise the code ayway.)
And of course there are all those algorithms for which recursion is by far the simplest and safest implementation - eg traversing an arbitrary tree structure - in which cases the overhead is a good trade-off.

[Schol-R-LEA]

@JamesCherrill : The standard Python implementation doesn't do TCO by default - Guido had doctrinal problems with it because he felt it makes stack traces effectively impossible - but there are several implementations of decorators which will force tail calls to be optimized in various ways. The most widely used on appears to the one maintained by ActiveState (though it isn't specific to their implementation of Python). This simple one seems easy to find as well. This blog post discusses the development of such a decorator in detail.

[sritaa]

At the most fundamental level, a recursive function is essentially a function that calls itself.

While this may initially seem perplexing, it's really not all that bad. Let's use the concept of factorials as an example.The best Python training focouses on such implementation.

A factorial is the product of an an integer and all of the positive integers below it. For example, 3! is 3×2×1.

So let's write a recursive function that calculates a factorial.

def factorial(n):
return 1 if n == 0 else n*factorial(n - 1)
This program takes a number n, and checks if it is 0. If the number is not 0, it returns the number n and calls the function again, except this time n is decremented.

So factorial(3) would run like this:

3≠0. return 3factorial(2).
2≠0. return 32factorial(1).
1≠0. return 321factorial(0).
0=0. return 321*1, or return 6.