Recursion means iteration. A function is called recursive, if the body of function calls the function itself until the condition for recursion is true. Thus, a Python recursive function has a termination condition.
In other words Recursion means calling a function itself again and again. Recursion is one of the most powerful tools in programming languge.
Why does a recursive function in Python has termination condition?
Well, the simple answer is to prevent the function from infinite recursion.
When a function body calls itself with any condition, this can go on forever resulting an infinite loop or recursion. This termination condition is also called base condition.
Is there any special syntax for recursive functions?
The answer is NO.
In Python, there is no syntactic difference between functions and recursive functions. There is only a logical difference.
Advantages of Python Recursion
- Reduces unnecessary calling of function, thus reduces length of program.
- Very flexible in data structure like stacks, queues, linked list and quick sort.
- Big and complex iterative solutions are easy and simple with Python recursion.
- Algorithms can be defined recursively making it much easier to visualize and prove.
Disadvantages of Python Recursion
- Logical but difficult to trace and debug.
- Requires extra storage space. For every recursive calls separate memory is allocated for the variables.
- Recursive functions often throw a Stack Overflow Exception when processing or operations are too large.
Important points related to recursion:
- There must be a terminating condition in the program which will marks the end of the process. (if not the process will get in an infinte loop)
- Each time a new recursive call is made a new memory space is allocated to each local variable used by the recursive function. or we can say that during each recursive call the local variables used in the function gets a different values having the same name.
- The values in the recursive function are pushed onto the stack with each call to the function and all these values are available to the function call when they are poped from the stack.