JustToThePoint English Website Version
JustToThePoint en español
JustToThePoint in Thai

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.

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

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
There are 10 types of people in this world, those who understand binary and those who dont.

There are 10 types of people in this world, those who understand binary and those who dont.

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.

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
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)
HanoySolving

HanoySolving

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

Towers of Hanoi

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
Life is like sudoku, all you need just place some things at the right place at the right time and then everything else will fall at its right place!

Life is like sudoku, all you need just place some things at the right place at the right time and then everything else will fall at its right place!

    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()
sodukuSolver

sodukuSolver

Bitcoin donation

JustToThePoint Copyright © 2011 - 2022 Anawim. ALL RIGHTS RESERVED. Bilingual e-books, articles, and videos to help your child and your entire family succeed, develop a healthy lifestyle, and have a lot of fun.

This website uses cookies to improve your navigation experience.
By continuing, you are consenting to our use of cookies, in accordance with our Cookies Policy and Website Terms and Conditions of use.