Question

Implement in Scheme Euclid’s algorithm computing the greatest common divisor of two integers as a tail recursive function.

What is the class of arithmetic functions that can be written in tail recursive way? Hint: Generalize out of examples you are familiar with.

Answer 1

Tail Recursive function are the functions in which recursive step is the last step of the function.

Below is the implementation of gcd function using tail recursion

#include <bits/stdc++.h>
using namespace std;
// gcd recursive function
int gcd(int a, int b)
{
//base condition
   if (b == 0)
       return a;
   //recursive step
   return gcd(b, a % b);
  
}

int main()
{

cout<<"Gcd of (8,10) is:";
cout<<gcd(8,10)<<endl;
}

Class of arithmetic functions which can be written in tail recursive way are is which output of recursive call completely dependent on same recursive function call with just other parameters passed.