Recursive Functions
Explore the core concepts of recursive functions, including how they call themselves, the importance of termination conditions, and their essential properties. Understand why recursion must change its state and how it differs from iterative solutions. This lesson prepares you to implement classic recursive problems such as factorials, greatest common divisor, Fibonacci numbers, permutations, and the Tower of Hanoi.
We'll cover the following...
Introduction
The function that calls itself directly or indirectly is known as a recursive function. The recursive method consists of two parts: the termination condition and the body. Both of them are explained below:
Termination condition
One or more terminating conditions are often present in a recursive system. It’s the condition where the function does not call itself.
Body The body of the recursive method contains the core logic of the method. It also includes the recursion expansion argument that invokes the method.
Properties of a recursive algorithm
There are three important properties of a recursive algorithm:
-
A recursive algorithm must have a termination condition.
-
A recursive algorithm must change its state, and shift the state toward the termination condition.
-
A recursive algorithm must be capable of calling itself.
Note: The recursive method can run forever if there is no termination condition, eventually consuming all of the stack memory.
Because of stack overheads, a recursive program runs slower. If an iterative approach (using loops) will achieve the same result as recursion, we can use it instead of recursion to minimize stack overhead.
