Recursion in Python
Recursion is a programming technique where a function calls itself either
directly or indirectly to solve a problem by breaking it into smaller, simpler
subproblems.
In Python, recursion is especially useful for problems that can be divided
into identical smaller tasks, such as mathematical calculations, tree traversals or
divide- and- conquer algorithms.
Working of Recursion
A recursive function is just like any other Python function except that it calls
itself in its body. Let's see basic structure of recursive function:
def recursive_function(parameters):
if base_case_condition:
return base_result
else:
return recursive_function(modified_parameters)
Recursive function contains two key parts:
Base Case: The stopping condition that prevents infinite recursion.
Recursive Case: The part of the function where it calls itself with modified
parameters.
Example 1: Factorial Calculation
This code defines a recursive function to calculate factorial of a number,
where function repeatedly calls itself with smaller values until it reaches the base
case.
def factorial(n):
if n == 0 : # Base case
return 1
else: # Recursive case
return n * factorial(n - 1)
print(factorial(5))
Output
120
Explanation:
Base Case: W hen n == 0 , recursion stops and returns 1.
Recursive Case: Multiplies n with the factorial of n- 1 until it reaches the
base case.
Example 2: Fibonacci Sequence
This code defines a recursive function to calculate nth Fibonacci number,
where each number is the sum of the two preceding ones, starting from 0 and 1.
def fibonacci(n):
if n == 0 :
return 0
elif n == 1:
return 1
else:
return fibonacci(n- 1) + fibonacci(n- 2)
print(fibonacci(10 ))
pass by reference and pass by value in python
1. Pass by Value (with Immutable Objects):
W hen an immutable object (e.g., integers, floats, strings, tuples) is passed to a
function, a copy of the reference to that object is passed.
Since the object itself cannot be modified, any attempt to reassign the local
variable within the function will only make that local variable point to a new
object, leaving the original object outside the function unchanged.
def modify_immutable(num):
print(f"Inside function (before modification): {num}")
num = 10 0 # Reassigns the local 'num' to a new object
print(f"Inside function (after modification): {num}")
my_num = 50
modify_immutable(my_num)
print(f"Outside function: {my_num}")
Output
Inside function (before modification): 50
Inside function (after modification): 10 0
Outside function: 50
2. Pass by Reference (with Mutable Objects):
W hen a mutable object (e.g., lists, dictionaries, sets) is passed to a
function, a copy of the reference to that object is passed.
Since both the original variable and the function's local variable now point
to the same object in memory, any modifications made to the object
through the local variable within the function will directly affect the original
object outside the function.
def modify_mutable(my_list):
print(f"Inside function (before modification): {my_list}")
my_list.append(4) # Modifies the object in place
print(f"Inside function (after modification): {my_list}")
original_list = [1, 2, 3]
modify_mutable(original_list)
print(f"Outside function: {original_list}")
Output
Inside function (before modification): [1, 2, 3]
Inside function (after modification): [1, 2, 3, 4]
Outside function: [1, 2, 3, 4]