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.**

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.

**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.

**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

**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.

**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.

import numpy as np class Soduku: # The solution is inspired by NeuralNine, One Step! Code, and AskPython. 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()