Recursion in C

Recursion in C
Definition (Mathematical)
process of defining The entire class of

something in terms of objects are defined in objects can then be
itself, and is terms of other objects built up from a few
sometimes called of the same type. initial values and a
circular definition. small number of rules.
Definition (Computer Science)
useful in evaluating When a function calls

A recursive function is certain types of another function and
one which calls itself. mathematical that second function
function calls the third function
Syntax of Recursion
returntype recursive_func ([argument
list])
{
statements;
... ... ...
recursive_func ([actual argument]);
... ... ...
}
Problems Suitable for Recursive Functions
• One or more simple cases of the problem have a straightforward solution.
• The other cases can be redefined in terms of problems that are
closer to the simple cases.
• The problem can be reduced entirely to simple cases by calling the recursive
function.
• If this is a simple case
solve it
else
redefine the problem using recursion
10-6
Example: multiplication by addition
The simple case is “m*1=m.”
The recursive step uses the following equation:

“m*n = m+m*(n-1).”
10-7
Trace of Function multiply(6,3)
The recursive step.
The recursive step.
The simple case.
10-8
Terminating Condition
• The recursive functions always contains one or more terminating
conditions.
• A condition when a recursive function is processing a simple
case instead of processing recursion.
• Without the terminating condition, the recursive function may run

forever.
• e.g., in the previous multiply function, the if statement “if (n
== 1) …” is the terminating condition.
10-9
Types of Recursion
Direct Recursion Indirect Recursion
A function is said to be indirect recursive if
A function is said to be direct it calls another function and this new
recursive if it calls itself directly. function calls the first calling function
again.
int func1(int n)
{ if (n<=1)
int fibo (int n) return 1;
{ else
if (n==1 || n==2) return func2(n);
return 1; }
int func2(int n)
else
{
return (fibo(n-1)+fibo(n-2));
return func1(n);
}
}
Simple example
main()
{
printf(“This is an example of recursive function”);
main();
}
• When this program is executed, the line is printed repeatedly and

indefinitely.
• We might have to abruptly terminate the execution.
Factorial Calculation
long int fact(int n) /* non-recursive */
{
int t, ans;
ans = 1;
for(t=1; t<=n; t++)
ans = ans*t;
return(ans);
}
long int factr(int n) /* recursive */

{
int ans;
if(n==1) return(1);
ans = factr(n-1)*n; /* recursive call */
return(ans);
}
Implementation of Factorial recursion using
Stack
Recursive version of power function
double power(double val, unsigned pow)
{
if(pow == 0) /*pow(x, 0) returns 1*/
return(1.0);
else
return(power(val, pow-1)*val);
}
How recursive functions works???
When a function calls itself, a new set of local

variables and parameters are allocated storage
on the stack, and the function code is executed
from the top with these new variables.
A recursive call does not make a new copy of

the function. Only the arguments are new.
As each recursive call returns, the old local

variables and parameters are removed from
the stack and execution resumes at the point
of the function call inside the function.
Summing up the elements of an array
Algorithm Design:
1. If we have only one element, then the sum is simple.
2. Otherwise, we use the sum of the first element and the sum
of the rest.
int sum(int first,int last,int array[])

{ if (first == last)
return (array[first]);
return(array[first]+sum(first+1,last,array));
}
For example:
Sum(1 8 3 2) = 1 + Sum(8 3 2) =
8 + Sum(3 2) =
3 + Sum (2)=
2
3+2=5
8 + 5 = 13
1 + 13 = 14
Answer = 14
Recursive Version of Fibonacci Series
int fib(int num) /*Fibonacci value of a number */
{
switch(num)
{ case 0: return(0);
break;
case 1: return(1);
break;
default: /*Including recursive calls */
return(fib(num - 1) + fib(num - 2));
break;
}
}
Pros and cons!!!
• No significant reduction in code size.
• No improvement in memory utilization.
• Recursive versions of most routines may execute a bit slower than their
iterative equivalents because of the overhead of the repeated function
calls.
• The main advantage to recursive functions is that you can use them to
create clearer and simpler versions of several algorithms.
• Recursion makes program elegant and more readable.
• Every recursion can be modeled into a loop.
Precaution!!!
When writing recursive functions, you must have an if statement

somewhere to force the function to return without the recursive call
being executed.
If you don't, the function will never return once you call it.
Program to find the sum of natural numbers using recursion
#include <stdio.h>
int sum(int n);
int main()
{ int number, result;
printf("Enter a positive integer: ");
scanf("%d", &number); Enter a positive integer: 3
sum = 6
result = sum(number);
printf("sum = %d", result); return 0; }
int sum(int num)
{ if (num!=0)
return num + sum(num-1); // sum() function calls itself
else
return num; }
Program to find GCD using recursion
#include <stdio.h>
int hcf(int n1, int n2);
int main()
{ int n1, n2;
printf("Enter two positive integers: "); Enter two positive
integers: 366 60
scanf("%d %d", &n1, &n2); G.C.D of 366 and 60 is 6.
printf("G.C.D of %d and %d is %d.", n1, n2, hcf(n1,n2));
return 0; }
int hcf(int n1, int n2)
{ if (n2 != 0)
return hcf(n2, n1%n2);
else return n1;
}
Thank You......

Recursion in C

Uploaded by

Copyright:

Available Formats

Recursion in C

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Recursion in C

Uploaded by

Copyright:

Available Formats

Recursion in C

process of defining The entire class of

useful in evaluating When a function calls

The simple case is “m*1=m.”

The recursive step uses the following equation:

The recursive step.

The recursive step.

The simple case.

• Without the terminating condition, the recursive function may run

• When this program is executed, the line is printed repeatedly and

long int factr(int n) /* recursive */

When a function calls itself, a new set of local

A recursive call does not make a new copy of

As each recursive call returns, the old local

int sum(int first,int last,int array[])

When writing recursive functions, you must have an if statement

You might also like