Become proficient with recursion by implementing the two algorithms below, and m
ID: 3869567 • Letter: B
Question
Become proficient with recursion by implementing the two algorithms below, and manipulating linked lists with recursion. Description of Fibonacci function: The Fibonacci sequence is the series of integers 0, 1, 1, 2,3,5, 8, 13, 21, 34, 55,... Note that each element in the series is the sum of the preceding two items. The formula for calculating the nth number of the sequence is given by: fib (n) = {n, if n = 0 or 1 fib (n - 1) + fib (n - 2) n > 1 Description of squareroot function: The following expression defines a function that calculates an approximation of the squareroot of a number, starting with an approximate answer (est), within the specified tolerance (tol) squareroot (n, est, tol) = {est, if |est^2 - n| lessthanorequalto tol squareroot (n, est^2 + n/2est, tol) if |est^2 - n| > tol Linked List manipulation using recursion: Perform the following operations on a linked list of words (strings). The words are to be stored using dynamically allocated memory (not an array). Write functions to perform the following tasks. Insertion Length Shortest and Longest word Contains a word (search) Deliverables: A complete program to calculate Fibonacci numbers, calculate squareroot s and manipulate linked lists of words. A program design sheet. Describe all functions necessary to implement your program. A sample calculation sheet. Show the expected values for both the Fibonacci series and the squareroot . Programming Log: Record the time required to design and implement your program.Explanation / Answer
//I CAN'T GIVE YOU WHOLE SOLUTION BUT I CAN GUIDE YOU TO THE SOLUTION.
//HERE FIRST TWO QUESTIONS ARE SOLVED AND three PART OF MANY SUBPARTS.
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
int fibonacci(int n)
{
if(n==1||n==0)//checking condition
return n;
if(n>=1)
return fibonacci(n-1)+fibonacci(n-2);
return -1;
}
/*************square root *********************/
float absolute(float f)//absolute function for taking modulus of a number
{
if(f<0)//check if no. is negative.
return -f;
else
return f;
}
int square_root(float n,float est,float tol)//square root function as per algorithm
{int cond;
cond=absolute((est*est)-n);//whole conditional value to be compared again and again contained in "cond" variable.
if(cond<=tol)
return est;
if(cond>tol)
return square_root(n,(est*est+n)/(2*est),tol);//est*est denotes power 2 on "est".
}
//*****************linked list*********************/
struct node//a linked list basic quantity to contain data and pointer named node
{
char data[MAX];//to hold words array is defined.
struct node* next;//pointer to next node
};
struct node *start=NULL;//globally declared start ,pointer to first node
void insert(char key[])
{ int i;
struct node *prev;//to hold previous node address
struct node *ptr;//to point current address of visiting node
struct node *temp;// pointer to dynamically allocated memory
temp= (struct node*) malloc(sizeof(struct node*));//dynamically allocating a memory
if(start==NULL)//check if list is empty
start=temp;
else
{
ptr=start;
while(ptr->next==NULL)
{
prev=ptr;
ptr=ptr->next;//point to next node
}
prev->next=temp;//give address of new node added to link-pointer of previous node
}
for(i=0;key[i]!='/0';i++)
temp->data[i]=key[i];//copying whole data to node
temp->next=NULL;
}
int search(char key[])//search function for word in the list
{struct node *temp;
int i;
while(temp->next!=NULL)
{for(i=0;key[i]!='/0';i++)
{
if(temp->data[i]==key[i])//in each node every character is matched with searching word value
return temp;
else
temp=temp->next;
}
}
return -1;//if not found return -1
}
int length()//to calculate length of linked list
{struct node *temp;
int length=0;
while(temp->next==NULL)//loop till linked till does'nt end
{
temp=temp->next;
length++;
}
return length;//lentgh of list
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.