#1 2020-09-13 08:15:24

Will89T64
Member
From: Canada, Windsor
Registered: 2020-09-13
Posts: 2

Click to share on Facebook (Opens in new window)


Posted on Thursday January 01, 1970


Posted on Thursday January 01, 1970


Posted on Thursday January 01, 1970


Posted on Thursday January 01, 1970


Posted on Thursday January 01, 1970


Posted on Thursday January 01, 1970


Posted on Thursday January 01, 1970

Collection of useful recursive functions.
Filed under: ,  — 2 Comments        March 31, 2011                 The elegant recursive solution to a problem is most of the times invaluable.
Although the iterative solution of that problem is likely to have a better  space  and time complexity, it is often preferred to use the recursive version for clarity and simplicity.
It is remarkable how easily a problem can be solved by use of a recursive manner.
In this article we will try to record a collection of useful recursive functions:  The following recursive function calculates the function N.
using  the standard  recursive definition.
It returns the correct value when called with N non-negative and small enough so that N.
can be represented as an integer type ‘int’.
int factorial (int N) {   if (N == 0) return 1;    return N * factorial (N-1); } The following recursive function was developed as an algorithm by Euclid 2000 years ago.
It is considered one of the oldest known algorithms and can be used for finding the greatest  common divi sor of two numbers.
int gcd (int m, int n) {   if (n == 0) return m;    return gcd (n, m % n); } The following recursive function can be used to count the nodes of a singly linked list.
int count (link x) {   if (x == 0) return 0;    return 1 + count (x->next); } The following recursive function can traverse all nodes in a singly linked list and process each node separately th rough  a processing function.
void traverse (link h, void visit (link)) {   if (h == 0) return;    visit (h);    traverse (h->next, visit); } The following recursive function works like the above but with the only difference being that it visits the nodes of a singly linked list in reverse order.
void traverseR (link h, void visit (link)) {   if (h == 0) return;    traverseR (h->next, visit);    visit (h); } The following recursive function removes from a singly linked list all nodes that have a given value.
void remove (link &x, Item v) {   while (x != 0 && x->item == v) {     link t = x;     x = x->next;     delete t;   }    if (x != 0)     remove (x->next, v); } The following function divides an array a[l], …, a[r] to a[l], …, a[m] and a[m+1], …, a[r].
Then, it finds the maximum element in each of the two parts (recursively), and returns the larger of the two as a maximum element in the overall array.
If the array size is even, both parts have the same size.
However, if it is odd, the sizes of the two parts of the array differ by 1.
Also.

It is worth mentioning that for the data type ‘Item’

we must have overloaded the comparison operator ‘>’ to run the following function.
Item max (Item a[], int l.

Int r) {   if (l == r) return a[l];    int m = (l+r) / 2;     Item u = max (a

l, m);   Item v = max (a, m+1, r);    if (u > v)     return u;   else     return v; } The following function provides a recursive solution to the Towers of Hanoi.
Void hanoi (int N.

Int d) {  if (N == 0) return;   hanoi (N-1

-d);  shift (N, d);     hanoi (N-1, -d); } The following “divide and conquer” recursive function can be used to design marks on a ruler.
More  specifically , to design the marks on a ruler, we first design the appropriate signs in the left half, then the longest mark in the middle, and then the appropriate signs in the right half.
void rule (int l, int r, int h) {   int m = (l+r) / 2;    if (h > 0) {     rule (l, m, h-1);     mark (m, h); // painting function.
rule (m, r, h-1);   } } The following recursive function can be used to generate a sequence of Fibonacci numbers.
However, it is not such a good solution because whenever it is called, it starts to count from  the beginning  throughout the sequence.
In particular, it has not got a history or memory to improve the response time of the function in the future.
int F (int i) {   if (i < 1) return 0;   if (i == 1) return 1;    return F (i-1) + F (i-2); } The following recursive function can be used to generate a sequence of Fibonacci numbers.
This  implementation , however, is a better solution than the previous one because it retains memory (Dynamic Programming) from which it can derive the results directly in future calls without having to recalculate a sequence from the beginning.
int F (int i) {   static int knownF[maxN];    if (knownF[i] != 0) return knownF[i];    int t = i;    if (i < 0) return 0;    if (i > 1) t = F (i-1) + F (i-2);    return knownF[i] = t; } The following recursive function accepts a link to a binary tree and process each node of the tree.
As it is now, the code implements the prefix tree traversal.
If you move the call of function ‘visit’ between the recursive calls we will have infix traversal of the tree.
But, if you move the call of function ‘visit’ after the recursive calls, we will have postfix traversal of the tree.
void traverse (link h, void visit (link)) {   if (h == 0) return;    visit (h);   traverse (h->l, visit);   traverse (h->r, visit); } The following recursive function can be used to count the nodes of a binary tree.
int count (link h) {   if (h == 0) return 0;    return count (h->l) + count (h->r) + 1; } The following recursive function can be used to calculate the height of a binary tree.
int height (link h) {   if (h == 0) return -1;    int u = height (h->l), v = height (h->r);    if (u > v)     return u+1;   else     return v+1; } The following recursive function is applied onto a graph and it actually implements the method of depth-first  search .
To visit all the nodes connected to node k of a graph, we note that node as the node that we have visited and then visit (recursively) all the nodes we have not visited and are included in the adjacency list of k.
void traverse (int k, void visit (int)) {   visit (k); visited[k] = 1;    for (link t = adj[k]; t != 0; t = t->next)     if (!visited[t->v]) traverse (t->v, visit); }           Rate this:.
Share this:.
Click to share on Facebook (Opens in new window).

Click to share on LinkedIn (Opens in new window)
Click to share on Twitter (Opens in new window)
Click to print (Opens in new window)
Click to email this to a friend (Opens in new window)

Like this:.
Like   Loading.
Related.
Tags: , , factorial, greatest common divisor, hanoi, , ,     .

Comments RSS feed                   2 Comments:

E.
Chatzikyriakidis            March 31, 2011 at 20:12           The truth is that I have omitted many recursive  implementations  ????.

Pantelis Koukousoulas            March 31

2011 at 18:54           You have, I think, omitted the most useful application of modern recursion and perhaps the only widely used in practice (at least in C / C++) : recursive descent parser ????.
Leave a  Reply Cancel  reply.
Enter your comment here.
Fill in your details below or click an icon to log in:.
Email  (Address never made public)                 Name                 Website                                                            You are commenting using your WordPress.com account.
( Log Out /     )                                                             You are commenting using your Google account.
( Log Out /     )                                                             You are commenting using your Twitter account.
( Log Out /     )                                                             You are commenting using your Facebook account.
( Log Out /     )                             Cancel   Connecting to %s             Notify me of new comments via email.
Notify me of new posts via email.

« Implementation of algorithm for converting an expression from infix to postfix notation
Implementation of algorithm for the calculating of prefix expressions

».
(79).
(21).
(15).
(26).
(4).
(7).
(55).
(24).
(4).
(16).
(14).
(4).
(7).
(10).
(78).
(11).
(9).
(1).
March 2011      M  T  W  T  F  S  S           123456      78910111213      14151617181920      21222324252627      28293031           « Feb     May ».
(2).
(4).
(1).
(1).
(2).
(1).
(1).
(1).
(2).
(1).
(9).
(1).
(8).
(1).
(1).
(2).
(4).
(7).
(1).
(1).
(1).
(8).
(12).
(1).
(2).
(1).
(2).
(1).
(2).
(1).
(1).
(4).
(20).
(13).
(5).
(2).
(10).
(13).
(10).
(10).
(20).
287,006 hits.
Send to Email Address          Your Name       Your Email Address                              Cancel       Post was not sent - check your email addresses.
Email check failed.

Please try again          Sorry

your blog cannot share posts by email.
%d  bloggers like this:.

Offline

W88top

Board footer

Powered by FluxBB