In recursive problem solving , a problem is repeatedly broken down into similar subproblems, until the subproblems can be directly solved without further breakdown.
Recursive Functions
There are two types of entities related to any function—the function definition, and any current execution instances
A function definition is a “cookie cutter” from which any number of execution instances can be created.
A recursive function is often defined as “a function that calls itself.” Recursive function execution instance refers to the creation of a new execution instance of the same function during its execution. Every time a call to a function is made, another execution instance of the function is created. Thus, while there is only one definition for any function, there can be any number of execution instances.
Iteration(General function call) vs. recursion
In the sequence of function calls described in the figure, the following events occur:
- An execution instance of function A is created and starts executing.
- When the call to function B is encountered, the execution instance of function A is suspended, and a new execution instance of function B is created and begins executing.
- Similarly, when the function call to function C is reached, the execution instance of function B is suspended, and a new execution instance of function C is created and starts executing.
- In this particular case, function C does not make any further function calls. It executes until it reaches its termination point and returns control to the function that called it, which is function B.
- Function B resumes its execution and continues until it reaches its termination point, returning control to function A.
- Finally, function A completes its execution and terminates, returning control to wherever it was initially called from.
Recursive Function Execution Instances
- Now, let's consider the scenario where function A is a recursive function, meaning it includes a call to itself in its definition.
- Each current execution instance of function A will generate a new execution instance of function A, as depicted in Figure. These execution instances are essentially clones of each other since they originate from the same function definition. Consequently, the function calls occur in the same location in each execution instance.
- It's important to note that a series of recursive function instances exhibit a similar execution pattern to a series of non-recursive instances. However, the difference lies in the fact that recursive instances are identical clones of each other due to their shared function definition.
- If a recursive function were defined in a way that it unconditionally calls itself, every execution instance would indefinitely call another instance, resulting in an infinite recursion similar to an infinite loop. Therefore, well-designed recursive functions include conditional statements to ensure that the chain of function calls eventually terminates.
Example:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
This recursive factorial function calculates the factorial of a non-negative integer n. If the value of n is 0, it returns 1 as the base case. Otherwise, it recursively calls itself with n - 1 and multiplies the result by n. The sequence of function execution instances generated for the factorial of 4 is given
The following sequence of function execution instances is created:
- factorial(4) calls factorial(3)
- factorial(3) calls factorial(2)
- factorial(2) calls factorial(1)
- factorial(1) calls factorial(0)
- factorial(0) returns 1 (base case)
At this point, the evaluation of the suspended expressions can proceed:
- factorial(1) returns 1 * 1 = 1
- factorial(2) returns 2 * 1 = 2
- factorial(3) returns 3 * 2 = 6
- factorial(4) returns 4 * 6 = 24
Finally, the value 24 is returned as the result of the original function call factorial(4).