# Recursion in Python

Python supports recursion. It means that functions can call themselves within their definitions. Recursion is a method of solving a problem in terms of a simpler version of itself.

• Let’s calculate the factorial of a number. The factorial of a number is the product of all the integers from 1 to that number, i.e., n!= n * (n-1) * (n-2) *… 1
from rich import print
def factorial(n):
if n==1: # What is the base case? When can I no longer continue? Answer: I can no longer continue when the number is one.
return 1
else: # What do I need to do in each iteration? The solution depends on solutions to smaller instances of the same problem.
return n*factorial(n-1)

if __name__ == "__main__":
number = 4
print("The factorial of", number, "is", factorial(number), ".") # The factorial of 4 is 24.

• Next, we are going to generate the Fibonacci sequence. The Fibonacci numbers form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.
def fibonacci(n):
if n<2:  # What is the base case? n = 0 and 1.
return n
return fibonacci(n - 1) + fibonacci(n - 2) # What do I need to do in each iteration?
if __name__ == "__main__":
print([fibonacci(n) for n in range(20)]) # It returns [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

• Reverse a string is a common introductory programming problem.
def reverseString(myString):
if len(myString)==0:  # What is the base case? When can I no longer continue? The string is empty.
return myString
else:  # What do I need to do in each iteration? The solution depends on solutions to smaller instances of the same problem.
return myString[-1] + reverseString(myString[:-1])
if __name__ == "__main__":
myString = "Whatever"
print("The reverse of", myString + "is [red]" + reverseString(myString) + "[/red].") # The reverse of Whateveris revetahW.

• A palindrome is a word, sentence or a number that reads the same backward or forward. We are going to write a recursive function which detects whether a string is a palindrome or not.
def ispalindrome(word):
if len(word) < 2: # What is the base case? A word with 0 or 1 character is a palindrome.
return True
if word[0] != word[-1]: # word[-1] is the last element in word. If the first character and the last character are not the same, then it is not a palindrome.
return False
return ispalindrome(word[1:-1])
if __name__ == "__main__":
lista = ["redivider", "amazing", "deified", "palindrome", "whatever", "civic", "radar", "level", "rotor", "kayak"]
print([ispalindrome(word) for word in list]) # [True, False, True, False, False, True, True, True, True, True]
print(', '.join(list(map(lambda w : w + " is a palindrome" if ispalindrome(w)==True else w + " is not a palindrome", lista ))))


redivider is a palindrome, amazing is not a palindrome, deified is a palindrome, palindrome is not a palindrome, whatever is not a palindrome, civic is a palindrome, radar is a palindrome, level is a palindrome, rotor is a palindrome, kayak is a palindrome.

• Let’s convert from decimal to binary.
def decBinary(n, result=""):
if int(n) == 0:
return result
else:
return decBinary(n // 2, str(n % 2) + result) # It divides the number by two and write down the remainder, e.g. 22 divided by 2 = 11 remainder 0. 11 divided by 2 = 5 remainder 1...
if __name__ == "__main__":
number = 314
print("The binary of", number, "is", decBinary(number)) # The binary of 314 is 100111010


To run or debug our function in VS Code, select Run and Debug on the Debug start view or press F5. As soon as a debugging session starts, the DEBUG CONSOLE panel is displayed and shows debugging output. Breakpoints in the editor margin are normally shown as red-filled circles.

• Next, we are going to create a function that calculates the sum of a list of numbers.
def sumList(listNumbers):
if len(listNumbers) == 0:
return 0
else:
return listNumbers[0] + sumList(listNumbers[1:])
if __name__ == "__main__":
print(sumList([1, 4, 2, 0, 7])) # 14

• Towers of Hanoi is a puzzle that consists of three pegs or rods and a number of disks. The goal is to move the stack of disks from peg A (source) to peg C (target) by moving one disk at a time and never placing a larger disk on top of a smaller one.
class Towers: # This class represents the three pegs or rods.
def __init__(self, disks=3):
self.disks = disks # Number of disks.
self.towers = [[], [], []] # A list of three lists representing the three pegs or rods. Each one of them contains all the disks that are placed on it.
self.towers[0] = [i for i in range(self.disks, 0, -1)] # If self.disks=3 (default value), self.towers[0] = [3, 2, 1]
self.towers[1] = []
self.towers[2] = []

def draw_digits(self, digit): # It is an auxiliary method to draw.
GREEN = '\033[92m'
BLUE = '\033[94m'
YELLOW = "\033[33m"
ENDC = '\033[0m'
if digit==1:
return GREEN + str(digit) + ENDC
elif digit==2:
return BLUE + str(digit) + ENDC
else:
return YELLOW + str(digit) + ENDC

def draw(self): # It draws the pegs and its disks.
output = ""
for i in range(self.disks, -1, -1): # It starts at the list's end.
for j in range(3):
if len(self.towers[j]) > i:
output += " " + self.draw_digits(self.towers[j][i])
else:
output += "  "
output += "\n"

print(output + "‐‐‐‐‐‐-")

def move(self, source, target): # It moves a disk from a source peg or rod to the target one.
disk = self.towers[source].pop() # We take the last disk (-1) from self.towers[source].
self.towers[target].append(disk) # And add it to the end of self.towers[target].

class TowersHanoi(): # This class represents the game.
def __init__(self, disks=3):
self.towers = Towers(disks) # It has a key attribute named self.towers. It is an instance of our class Towers.
self.disks = disks # This attribute stores the number of disks.

def solve(self): # It solves the game.
self.solve_tower_of_hanoi(self.disks, 0, 2, 1)

def solve_tower_of_hanoi(self, n, start_tower, dest_tower, aux_tower):
if n > 0: # If n==0, it is the base case, we do nothing. Otherwise...
# We solve the Towers of Hanoi's game with n - 1 disks from start_tower to aux_tower.
self.solve_tower_of_hanoi(n - 1, start_tower, aux_tower, dest_tower)
# Once it is solved, we can move the last "n" disk (the bigger one), from start_tower to dest_tower.
self.towers.move(start_tower, dest_tower)
# We draw the actual state of the game.
self.towers.draw()
# Once the bigger "n" disk has been placed in its right position, we move the remaining n - 1 disks from aux_tower to dest_tower.
self.solve_tower_of_hanoi(n - 1, aux_tower, dest_tower, start_tower)


if __name__ == "__main__":
t = TowersHanoi()
t.solve()


• Soduku solver. A Soduku is “an easy to learn logic-based number placement puzzle. […] It consists of 81 cells which are divided into nine columns, rows and regions. The task is now to place the numbers from 1 to 9 into the empty cells in such a way that in every row, column and 3×3 region each number appears only once,” Soduku-Space.com.

The solution is inspired by NeuralNine, One Step! Code, and AskPython.

import numpy as np
class Soduku:
def __init__(self, board):
# First, we delete whitespace (' ') and newlines ('\n')
lines = board.replace(' ','').replace('\n','')
# Second, we convert it to a list of integers
digits = list(map(int, lines))
# Remember that map(int, lines) returns a list of "integers" after applying the int() function.
# Third, we create an array, and give it a new shape. Basically, we turn it to a 9 x 9 array.
self.board = np.array(digits).reshape(9, 9)

# Is it a valid move to place number in (row, col)? If we find the same number in the same row, column, or in the same 3*3 matrix, it will return ‘false’. Otherwise, 'true' will be returned.
def is_valid_move(self, row, col, number):
for x in range(9):
if self.board[row][x] == number:
return False

for x in range(9):
if self.board[x][col] == number:
return False

corner_row = row - row % 3
corner_col = col - col % 3

for x in range(3):
for y in range(3):
if self.board[corner_row + x][corner_col + y] == number:
return False

return True


    def solve(self, row, col): # It tries to solve the Soduku.
# It checks if it has reached the 8th row and 9th column. So if this is the case, it returns True, it has solved the Soduku.
if col==9:
if row == 8:
return True
row += 1 # If the column is 9, then it moves to the next row and sets col to zero.
col = 0

if self.board[row][col] > 0: # If the current position of the grid (row, col) has a value greater than 0, it means that the cell is already filled, so we move on and try to solve the Soduku in (row, col+1).
return self.solve(row, col+1)

for num in range(1, 10): # We iterate from 1-9.
if self.is_valid_move(row, col, num): # If it is a valid move to place "num" in the current position of the board (row, col)...
self.board[row][col] = num # it stores num in this position

if self.solve(row, col+1): # And we try to solve the Soduku in (row, col+1)
return True # If we are here, we are lucky, we have already solved the Soduku.

self.board[row][col] = 0 # If we are here, it means that our assumption was wrong (we could not solve the Soduku by putting num in (row, col)), and we need to backtrack our steps, i.e. remove the number num from the current position of the board (row, col), and then we go for a different value

return False # We have tried everything in the book and failed miserably.

def draw(self): # It draws the board.
if self.solve(0, 0):
for row in range(9):
if row%3==0:
print("+‐‐‐‐‐‐-+‐‐‐‐‐‐-+‐‐‐‐‐‐-+")
for col in range(9):
if col==0:
print("| " + str(self.board[row][col]), end ="")
elif col==2 or col==5 or col==8:
print(" " + str(self.board[row][col]) + " |", end ="")
else:
print(" " + str(self.board[row][col]), end ="")
print()
if row==8:
print("+‐‐‐‐‐‐-+‐‐‐‐‐‐-+‐‐‐‐‐‐-+")

else:
print("There is no solution")

if __name__ == "__main__":
board = '''0 means the cells where no value is assigned'''
board =  """250030901
010004000
407000208
005200000
000098100
040003000
000360072
070000003
903000604"""
mySoduku = Soduku(board)
mySoduku.draw()
print()
board2 = """043080250
600000000
000001094
900004070
000608000
010200003
820500000
000000005
034090710"""
mySoduku2 = Soduku(board2)
mySoduku2.draw()


Bitcoin donation