RECURSION
A R U N A R U N I S T O
Recursion is a programming concept where a
function calls itself in order to solve a
problem. It's like a process that repeats itself
in a self-similar way. Think of it as a function
that keeps breaking down a problem into
smaller parts until it reaches a base case
where it can directly compute the solution.
Recursion is a powerful technique but needs
to be used carefully to avoid infinite loops or
stack overflow errors. It's particularly useful
for problems that can be broken down into
simpler, similar sub-problems, such as tree
traversal, sorting algorithms like quicksort,
and many mathematical algorithms.
#syntax
def <function_name>(<args>):
if <condition>: #-> Base case
<statement>
else:
<recursive case>
Sample Programs & Definitions:
Recursion with string:
1. Reverse String:
def reverse_str(text, result=""):
if text == "":
return result
result+=text[-1]
return reverse_str(text[:-1], result)
Function named reverse_str that takes two
parameters: text (the string to be reversed)
and result (used for accumulating the
reversed string during recursion). The result
parameter is initialized with an empty string
by default.
if text == "": This line checks if the text
parameter is an empty string, indicating the
base case of the recursion where there are
no characters left to reverse. If text is
empty, the function returns the result,
which contains the reversed string.
result += text[-1]: This line appends the last
character of the text to the result string. It
uses negative indexing (text[-1]) to access
the last character of the string text.
return reverse_str(text[:-1], result): text[:-1]
is the substring of text excluding the last
character. This effectively reduces the
length of text by one character in each
recursive call. result is passed along to
accumulate the reversed string.
2 Checks a string palindrome or not:
def palindrome_str(text):
if text == "":
return True
if text[0] == text[-1]:
return palindrome_str(text[1:-1])
return False
def palindrome_str(text): This line defines a
function named palindrome_str that takes
one parameter text, which is the string to be
checked for being a palindrome.
if text == "": This line checks if the input
string text is empty. If the string is empty, it
means it's a palindrome by definition (as an
empty string reads the same forward and
backward), so the function returns True.
if text[0] == text[-1]: This line checks if the
first character of the string (text[0]) is equal
to the last character of the string (text[-1]).
This comparison verifies if the string begins
and ends with the same character.
return palindrome_str(text[1:-1]): This line is
the recursive step. If the first and last
characters are equal, it calls the
palindrome_str function with a modified
substring text[1:-1], which is the original
string without its first and last characters.
This recursive call continues until the base
case is reached (an empty string) or until it
finds a pair of characters that are not equal.
return False: If the first and last characters
of the string are not equal, the function
immediately returns False, indicating that
the string is not a palindrome.
Recursion with integer:
1. Integer to binary
def int_to_bin(num, result=""):
if num == 0:
return result
result = str(num%2)+result
return int_to_bin(num//2, result)
Function named int_to_bin that takes two
parameters: num (the integer to be
converted to binary) and result (used for
accumulating the binary representation
during recursion). The result parameter is
initialized with an empty string by default.
if num == 0: This line checks if the num
parameter is equal to 0, which serves as the
base case for the recursion. If num is indeed
0, it means we have converted the entire
integer to binary, so the function returns the
accumulated binary representation stored in
result.
result = str(num % 2) + result: This line
calculates the remainder of num divided by
2 (i.e., num % 2), converts it to a string, and
appends it to the beginning of the result
string. This effectively builds the binary
representation from right to left.
return int_to_bin(num // 2, result): num // 2
calculates the integer division of num by 2,
effectively reducing the value of num by half
in each recursive [Link] is passed along
to accumulate the binary representation.
2. Reversing an integer:
def reverse_int(num, result=0):
if num == 0:
return result
digit = num%10
result = result*10+digit
return reverse_int(num//10, result)
A function named reverse_int takes two
parameters: num (the integer to be
reversed) and result (used for accumulating
the reversed integer during recursion). The
result parameter is initialized with 0 by
default.
if num == 0: This line checks if the num
parameter is equal to 0, which serves as the
base case for the recursion. If num is indeed
0, it means we have reversed the entire
integer, so the function returns the
accumulated reversed integer stored in
result.
digit = num % 10: This line calculates the last
digit of the integer by finding the remainder
of num divided by 10 (i.e., num % 10). This
digit will be added to the reversed number.
result = result * 10 + digit: This line updates
the result by multiplying it by 10 (shifting
digits one place to the left) and then adding
the last digit of the original number (digit).
This effectively builds the reversed integer.
return reverse_int(num // 10, result): num //
10 calculates the integer division of num by
10, effectively removing the last digit of num
in each recursive call. result is passed along
to accumulate the reversed integer.