Advanced Programming Logic

Recursion

[Link], AP (SG) / CSE

9791519152
bhuvaneswaran@[Link]
Introduction
 Recursion is an important concept in computer science.
 It is a foundation for many other algorithms and data structures.
 However, the concept of recursion can be tricky to grasp for many
beginners.

Recursion Rajalakshmi Engineering College 2

Questions?
 What is recursion? How does it work?
 How to solve a problem recursively?
 How to analyze the time and space complexity of a recursive
algorithm?
 How can we apply recursion in a better way?

Recursion Rajalakshmi Engineering College 3

Principle of Recursion
 Recursion is an approach to solving problems using a function that
calls itself as a subroutine.
 The trick is that each time a recursive function calls itself, it
reduces the given problem into subproblems.
 The recursion call continues until it reaches a point where the
subproblem can be solved without further recursion.

Recursion Rajalakshmi Engineering College 4

Principle of Recursion
 A recursive function should have the following properties so that it
does not result in an infinite loop:
• A simple base case (or cases) — a terminating scenario that does not use
recursion to produce an answer.
• A set of rules, also known as recurrence relation that reduces all other
cases towards the base case.
 Note that there could be multiple places where the function may
call itself.

Recursion Rajalakshmi Engineering College 5

Types of Recursions
 Direct recursion
 Indirect recursion

Recursion Rajalakshmi Engineering College 6

Direct Recursion
 In the direct recursion, the same function calls itself from its own
body.

Recursion Rajalakshmi Engineering College 7

Indirect Recursion
 In indirect recursion the function invokes some other function
which again invokes the function which has invoked it.
 That is, it creates a cycle of function calls.

Recursion Rajalakshmi Engineering College 8

Example
 An useful example of recursion is the evaluation of factorials of a
given number.
 The factorial of a number n is expressed as a series of repetitive
multiplications as shown below:
factorial of n = n (n - 1) (n - 2) . . . 1
 For example:
factorial of 4 = 4 × 3 × 2 × 1 = 24

Recursion Rajalakshmi Engineering College 9

Program
int fact(int n)
{
if(n ==0 || n == 1)
return 1;
else
return(n * fact(n - 1));
}

Recursion Rajalakshmi Engineering College 10

Explanation
 Let us see how the recursion works. Assume n = 5. Since the value of n is not 1,
the statement:
fact = n * factorial(n-l);
 will be executed with n = 5. That is,
fact = 5 * factorial(4);
 will be evaluated. The expression on the right-hand side includes a call to
factorial with n = 4. This call will return the following value:
4* factorial(3)
 Once again, factorial is called with n = 3. That is,
3 * factorial(2);
 will be evaluated. The expression on the right-hand side includes a call to
factorial with n = 2. This call will return the following value:
2 * factorial(1);
 Once again, factorial is called with n = 1. This time, the function returns 1.

Recursion Rajalakshmi Engineering College 11

Explanation
 The sequence of operations can be summarized as follows:
fact = 5 * factorial(4)

= 5 * 4 * factorial(3)

= 5 * 4 * 3 * factorial(2)

= 5 * 4 * 3 * 2 * factorial(1)

=5*4*3*2*1

= 120

Recursion Rajalakshmi Engineering College 12

Explanation
 Recursive functions can be effectively used to solve problems
where solution is expressed in terms of successively applying the
same solution to subsets of the problem.
 When we write recursive functions, we must have an if statement
somewhere to force the function to return without the recursive
call being executed.
 Otherwise, the function will never return.

Recursion Rajalakshmi Engineering College 13

Recursive evaluation of 5!

Recursion Rajalakshmi Engineering College 14

Program
#include <stdio.h>
int fact(int);
int main()
{
int n, f = 1;
scanf("%d", &n);
f = fact(n);
printf("%d", f);
return 0;
}

Recursion Rajalakshmi Engineering College 15

Program
int fact(int n)
{
if(n ==0 || n == 1)
return 1;
else
return(n * fact(n - 1));
}

Recursion Rajalakshmi Engineering College 16

Output
5
120

Recursion Rajalakshmi Engineering College 17

Sum of First n Natural Nos. (Bottom up - Iteration)
#include <stdio.h>

int main()
{
int n, i, sum = 0;
scanf("%d", &n);
for (i = 1; i <= n; i++)
sum = sum + i;
printf("%d", sum);
return 0;
}

Recursion Rajalakshmi Engineering College 18

Sum of First n Natural Nos. (Top down - Recursion)
#include <stdio.h>

int sum(int n)
{
if (n == 1)
return 1;
return sum(n - 1) + n;
}

int main()
{
int n;
scanf("%d", &n);
printf("%d", sum(n));
return 0;
}

Recursion Rajalakshmi Engineering College 19

Print nth Fibonacci Term (Recursion)
#include <stdio.h>

int fib(int n)
{
if (n == 0 || n == 1)
return n;
return fib(n - 1) + fib(n - 2);
}

int main()
{
int n;
scanf("%d", &n);
printf("%d", fib(n));
return 0;
}

Recursion Rajalakshmi Engineering College 20

Print a string in reverse order
 You can easily solve this problem iteratively, i.e. looping through
the string starting from its last character. But how about solving it
recursively?
 First, we can define the desired function as printReverse(str[0...n-
1]), where str[0] represents the first character in the string. Then
we can accomplish the given task in two steps:
• printReverse(str[1...n-1]): print the substring str[1...n-1] in reverse order.
• print(str[0]): print the first character in the string.
 Notice that we call the function itself in the first step, which by
definition makes the function recursive.

Recursion Rajalakshmi Engineering College 21

Code Snippet
void printReverse(const char *str)
{
if (!*str)
return;
printReverse(str + 1);
putchar(*str);
}

Recursion Rajalakshmi Engineering College 22

Time Complexity - Recursion
 You can easily solve this problem iteratively, i.e. looping through
the string starting from its last character. But how about solving it
recursively?
 First, we can define the desired function as printReverse(str[0...n-
1]), where str[0] represents the first character in the string. Then
we can accomplish the given task in two steps:
• printReverse(str[1...n-1]): print the substring str[1...n-1] in reverse order.
• print(str[0]): print the first character in the string.
 Notice that we call the function itself in the first step, which by
definition makes the function recursive.

Recursion Rajalakshmi Engineering College 23

Recursion to Iteration
 Sometimes it is desirable to implement the algorithm with
iteration instead of recursion, due to the constraint of memory
consumption or efficiency.

Recursion Rajalakshmi Engineering College 24

 Unfold Recursion
 Recursion could be an elegant and intuitive solution, when applied
properly.
 Nevertheless, sometimes, one might have to convert a recursive
algorithm to iterative one for various reasons.

Recursion Rajalakshmi Engineering College 25

Risk of Stackoverflow
 The recursion often incurs additional memory consumption on the
system stack, which is a limited resource for each program.
 If not used properly, the recursion algorithm could lead to
stackoverflow.
 One might argue that a specific type of recursion called tail
recursion could solve this problem.
 Unfortunately, not every recursion can be converted to tail
recursion, and not every compiler supports the optimization of the
tail recursion.

Recursion Rajalakshmi Engineering College 26

Efficiency
 Along with the additional memory consumption, the recursion
could impose at least the additional cost of function calls, and in a
worse case duplicate calculation, i.e. one of the caveats of
recursion.

Recursion Rajalakshmi Engineering College 27

Complexity
 The nature of recursion is quite close to the mathematics, which is
why the recursion appears to be more intuitive and
comprehensive for many people.
 However, when we abuse the recursion, the recursive program
could become more difficult to read and understand than the non-
recursive one, e.g. nested recursion etc.

Recursion Rajalakshmi Engineering College 28

Recursion vs Iteration
Criteria Recursion Iteration
Definition When a function calls itself When some set of instructions
directly or indirectly. are executed repeatedly.
Implementat Implemented using function Implemented using loops.
ion calls.
Format Base case and recursive relation Includes initializing, control
are specified. variable, termination condition,
and update of the control
variable.
Current Defined by the parameters Defined by the value of the
State stored in the stack. control variable.
Progression The function state approaches The control variable approaches
the base case. the termination value.

Recursion Rajalakshmi Engineering College 29

Recursion vs Iteration
Criteria Recursion Iteration
Memory Uses stack memory to store Does not use memory except
Usage local variables and parameters. initializing control variables.
Infinite It will cause stack overflow error It will cause an infinite loop if the
Repetition and may crash the system if the control variable does not reach
base case is not defined or is the termination value.
never reached.
Code Size Recursive code is generally Iterative code is generally bigger.
smaller and simpler.
Overhead Possesses overhead of repeated No overhead as there are no
function call. function calls.
Speed Slower in execution. Faster in execution

Recursion Rajalakshmi Engineering College 30

Queries?
Thank You…!