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,
/* * 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.
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.
- Apply for C Internship
- Practice BCA MCQs
- Practice Computer Science MCQs
- Check Computer Science Books
- Check C Books