[go: up one dir, main page]
Scribd
Upload
15 views5 pages

CH # 3 (Recursion)

The document discusses recursion, including properties of recursive functions like a base criteria and progressive approach. It provides examples of recursive functions to calculate factorials and Fibonacci sequences. Recursion involves defining a function in terms of itself through recursive calls that progress toward a base case, while iterative functions use loops.

Uploaded by

Muhammad Imran
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
15 views5 pages

CH # 3 (Recursion)

The document discusses recursion, including properties of recursive functions like a base criteria and progressive approach. It provides examples of recursive functions to calculate factorials and Fibonacci sequences. Recursion involves defining a function in terms of itself through recursive calls that progress toward a base case, while iterative functions use loops.

Uploaded by

Muhammad Imran
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
You are on page 1/ 5

Ch # 3 Recursion

Introduction to Recursion:
A function is recursive if a statement in the body of the function calls itself. Recursion is
the process of defining something in terms of itself. For a computer language to be
recursive, a function must be able to call itself.

Properties
A recursive function can go infinite like a loop. To avoid infinite running of recursive
function, there are two properties that a recursive function must have −
Base criteria − There must be at least one base criteria or condition, such that, when this
condition is met the function stops calling itself recursively.
Progressive approach − The recursive calls should progress in such a way that each time
a recursive call is made it comes closer to the base criteria.

For example, let us consider the function factr() shown below, which computers
the factorial of an integer. #include <stdio.h>
int factorial (int);
main()

{
int num, fact;
printf (“Enter a positive integer value: ");
scanf (“%d”, &num);
fact = factorial (num);
printf ("\n Factorial of %d =%5d\n", num, fact);
}

int factorial (int n)


{
int result;
if (n == 0)
return (1);
else
result = n * factorial (n-1);
return (result);
}
A non-recursive or iterative version for finding the factorial is as follows:
factorial (int n)
{
int i, result = 1;

if (n == 0)

return (result);
else
{
for (i=1; i<=n; i++)
result = result * i;
}
return (result);
}
The operation of the non-recursive version is clear as it uses a loop starting at 1 and
ending at the target value and progressively multiplies each number by the moving
product.
When a function calls itself, new local variables and parameters are allocated storage on
the stack and the function code is executed with these new variables from the start. A
recursive call does not make a new copy of the function. Only the arguments and
variables 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.
When writing recursive functions, you must have a exit condition somewhere to force the
function to return without the recursive call being executed. If you do not have an exit
condition, the recursive function will recurse forever until you run out of stack space and
indicate error about lack of memory, or stack overflow.

Differences between recursion and iteration:

• Both involve repetition.


• Both involve a termination test.
• Both can occur infinitely.
Analysis of Recursion
One may argue why to use recursion, as the same task can be done with iteration. The
first reason is, recursion makes a program more readable and because of latest enhanced
CPU systems, recursion is more efficient than iterations.

1. Time Complexity

In case of iterations, we take number of iterations to count the time complexity. Likewise,
in case of recursion, assuming everything is constant, we try to figure out the number of
times a recursive call is being made. A call made to a function is Ο(1), hence the (n)
number of times a recursive call is made makes the recursive function Ο(n).

2. Space Complexity

Space complexity is counted as what amount of extra space is required for a module to
execute. In case of iterations, the compiler hardly requires any extra space. The compiler
keeps updating the values of variables used in the iterations. But in case of recursion, the
system needs to store activation record each time a recursive call is made. Hence, it is
considered that space complexity of recursive function may go higher than that of a
function with iteration.

Factorial of a given number:


The operation of recursive factorial function is as follows:
Start out with some natural number N (in our example, 5). The recursive definition
is:
n = 0, 0 ! = 1 Base Case
n > 0, n ! = n * (n - 1) ! Recursive Case
Recursion Factorials:
5! =5 * 4! = 5 *___ = ____ factr(5) = 5 * factr(4) = __
4! = 4 *3! = 4 *___ = ___ factr(4) = 4 * factr(3) = __
3! = 3 * 2! = 3 * ___ = ___ factr(3) = 3 * factr(2) = __
2! = 2 * 1! = 2 * ___ = ___ factr(2) = 2 * factr(1) = __
1! = 1 * 0! = 1 * __ = __ factr(1) = 1 * factr(0) = __
0!=1 factr(0)=__
5! = 5*4! = 5*4*3! = 5*4*3*2! = 5*4*3*2*1! = 5*4*3*2*1*0! = 5*4*3*2*1*1 =120
We define 0! to equal 1, and we define factorial N (where N > 0), to be N *
factorial (N-1). All recursive functions must have an exit condition, that is a state when it
does not recurse upon itself. Our exit condition in this example is when N = 0.
Tracing of the flow of the factorial () function:

When the factorial function is first called with, say, N = 5, here is what happens:
FUNCTION: Does N = 0? No Function Return Value = 5 * factorial (4)
At this time, the function factorial is called again, with N = 4.

FUNCTION: Does N = 0? No Function Return Value = 4 * factorial (3) At this time, the
function factorial is called again, with N = 3.
FUNCTION: Does N = 0? No Function Return Value = 3 * factorial (2)
At this time, the function factorial is called again, with N = 2.

FUNCTION: Does N = 0? No Function Return Value = 2 * factorial (1) At this time, the
function factorial is called again, with N = 1. FUNCTION: Does N = 0? No Function
Return Value = 1 * factorial (0) At this time, the function factorial is called again, with N
= 0. FUNCTION: Does N = 0? Yes Function Return Value = 1

Now, we have to trace our way back up! See, the factorial function was called six
times. At any function level call, all function level calls above still exist! So, when we
have N = 2, the function instances where N = 3, 4, and 5 are still waiting for their
return values.
So, the function call where N = 1 gets retraced first, once the final call returns 0. So,
the function call where N = 1 returns 1*1, or 1. The next higher function call, where N
= 2, returns 2 * 1 (1, because that's what the function call where N = 1 returned). You
just keep working up the chain.
When N = 2, 2 * 1, or 2 was returned.
When N = 3, 3 * 2, or 6 was returned.
When N = 4, 4 * 6, or 24 was returned.
When N = 5, 5 * 24, or 120 was returned.
And since N = 5 was the first function call (hence the last one to be recalled), the value
120 is returned.

Fibonacci Sequence Problem:


A Fibonacci sequence starts with the integers 0 and 1. Successive elements in this
sequence are obtained by summing the preceding two elements in the sequence. For
example, third number in the sequence is 0 + 1 = 1, fourth number is 1 + 1= 2, fifth
number is 1 + 2 = 3 and so on. The sequence of Fibonacci integers is given below:
0 1 1 2 3 5 8 13 21 . . . . . . . . .

A recursive definition for the Fibonacci sequence of integers may be defined as follows:
Fib (n) = n if n = 0 or n = 1
Fib (n) = fib (n-1) + fib (n-2) for n >=2
We will now use the definition to compute fib(5):

You might also like