w3resource

Python Data Structures and Algorithms - Recursion: gcd of two integers

Python Recursion: Exercise-11 with Solution

Write a Python program to find the greatest common divisor (GCD) of two integers.

Sample Solution:-

Python Code:

def Recurgcd(a, b):
	low = min(a, b)
	high = max(a, b)

	if low == 0:
		return high
	elif low == 1:
		return 1
	else:
		return Recurgcd(low, high%low)
print(Recurgcd(12,14))

Sample Output:

2

Flowchart:

Flowchart: Recursion: gcd of two integers.

Visualize Python code execution:

The following tool visualize what the computer is doing step-by-step as it executes the said program:

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Python program to calculate the value of 'a' to the power 'b'.
Next: Python Math Exercise Home.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.

Python: Tips of the Day

Chunks a list into smaller lists of a specified size:

Example:

from math import ceil

def tips_chunk(lst, size):
  return list(
    map(lambda x: lst[x * size:x * size + size],
      list(range(0, ceil(len(lst) / size)))))

print(tips_chunk([1, 2, 3, 4, 5, 6], 3))

Output:

[[1, 2, 3], [4, 5, 6]]