Difference Between Recursion and Iteration in C

Question: Is Recursion in C Different from Iteration Implemented Through Loops

Answer: To understand the difference between Recursion and Iteration implemented through loops, let’s first consider a simple program,

/* down_recur.c -- program counts down ways */
#include <stdio.h>
void countdown(int);
 
int main(void)
{
    int num = 100;
    countdown(num);
 
    return 0;
}
 
void countdown(int count)
{
    if (count >= 1) {
        printf("%d\n", count);
        countdown(count--);
    }
}

Observe the output below, for simplicity, some portion of output is displayed, dots … indicate numbers in sequence,

100
99
98
97
96
95
.
.
.
6
5
4
3
2
1

Now, we try to perform the same job using loops, for example,

advertisement
advertisement
/*
 * diff_recur_and_loops.c -- program displays integers 100 through 1 using
 * loops
 */
#include <stdio.h>
int main(void)
{
    int num = 100;
 
    for (; num >= 1; num--) {
        printf("%d\n", num);
    }
    return 0;
}

Output of the above program is as follows,

100
99
98
97
96
95
.
.
.
6
5
4
3
2
1

Both outputs are same. Where’s the difference in two approaches? let’s unravel this, now.

Notice that each time ‘countdown()’ is called recursively, formal integer argument ‘count’ is created and it obtained copy of integer from previous recursive call of function ‘countdown()’. Therefore, there were created 101 integers with same name ‘count’, last one with value 0. Each ‘count’ is private/local to its function and so there’s no same name conflict. We know in C that when a function is called, it’s allotted a portion of temporary area called STACK for placing up there its private/local arguments, return addresses of calling functions etc. This way, for 101 recursive function calls to itself, there were created 101 STACKS, one for each function. Further, this caused recursion slow. Also, recursion exhausts systems important memory resources and might cause the program to abnormally aborted.

Also, we observed here that we must design some condition in recursive function which during successive recursive calls eventually fails and recursion stops. If type of recursive function isn’t void, each recursive call only after recursion stopped returns that type of value to its calling function.

advertisement

Now, we discuss same problem using loops. Here, we implemented for loop, just took one integer variable ‘num’ and performed the job efficiently with single variable. There were no trade-offs involved in creating separate STACK for every Iteration instead iterations used the modified single integer and performed the task efficiently.

However, b>we conclude that aside from creating its own local variables during each recursive call, recursion and loops are alike!

Sanfoundry Global Education & Learning Series – 1000 C Tutorials.

If you wish to look at all C Tutorials, go to C Tutorials.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.