Recursive function to the greatest common divisor of two positive numbers

Algorithm:

1. Start
2. Define a recursive function GCD that takes two parameters a and b
3. If b equals 0
   - Return a as the result
4. Otherwise
   - Return GCD(b, a mod b)
5. Input first number (num1)
6. Input second number (num2)
7. Call GCD function with num1 and num2
8. Display the result
9. End

Hello, dear reader! 👋

Thanks for visiting my blog! I’m a student just like you, sharing what I learn to help others with Python programming. I hope my posts are useful for your studies! 😊

If you find this post helpful, please leave a comment—even just a few emojis will make my day! 🐍✨ Your feedback keeps me motivated to create more content for everyone. 🚀

Happy programming!
— Abhin Krishna, S01, EB Department, MEC

Pseudocode:

FUNCTION GCD(a, b)
    IF b = 0 THEN
        RETURN a
    ELSE
        RETURN GCD(b, a MOD b)
    END IF
END FUNCTION

BEGIN
    PRINT "Enter the first number: "
    INPUT num1
    PRINT "Enter the second number: "
    INPUT num2
    
    result ← GCD(num1, num2)
    
    PRINT "The GCD of ", num1, " and ", num2, " is ", result
END

Program:

# Recursive function to find GCD using Euclid's algorithm
def gcd(a, b):
    # Base case: if b is 0, gcd is a
    if b == 0:
        return a
    # Recursive case: call gcd with b and a % b
    return gcd(b, a % b)

# Input two numbers
num1 = int(input("Enter the first number: "))
num2 = int(input("Enter the second number: "))

# Calculate the GCD using recursion
result = gcd(num1, num2)

# Print the result
print(f"The GCD of {num1} and {num2} is {result}")

Flowchart:

flowchart TD A([Start]) --> B[/Input first number num1/] B --> C[/Input second number num2/] C --> D[Call GCD function with num1, num2] subgraph GCD_Function[GCD Function] E{Is b = 0?} --> |Yes| F[Return a] E --> |No| G[Return GCD_Function b, a MOD b] G --> E end D --> GCD_Function F --> H[/Display GCD result/] H --> I([End])

Important!
If you find any mistakes in my code or flowchart, please comment below this post. I will be happy to correct them and clear up any doubts you may have.

Recursive function to the greatest common divisor of two positive numbers