The World of Recursion in Computing
ESC101:
Fundamentals of
Computing
Recursion
Nisheeth
Recursion
Process of solving a problem
using solutions to “smaller”
versions
of the same problem!
You have already encountered recursion in mathematics
Factorial function is defined in terms of factorial itself!
Proof by induction is basically a
recursive proof
Claim
: 1 + 2 + 3 + … + n = n(n+1)/2
Proof
:
Base case
: for n = 1 true by inspection
Inductive case
: (1 + … + n) = (1 + … + n-1) + n = (n-1)n/2 + n = n(n+1)/2
Notice that we need a base case and recursive case
In case of factorial, fac(0) was the
base case
.
This is true when writing recursive functions in C language as well
2
We used the proof for the
case n-1 to prove the case n
Mutual Recursion
3
Two functions calling each other in a recursive fashion
Note: The above example is not the most efficient way
to check if a number of even or add but just an illustration
of mutual recursion
About Recursion
Recursion can allow us to write very elegant code
Very easy to understand what is going on by just reading function definition
Sometimes you can just “copy” the function definition into code
Careful: do not forget to write down the base case
Will go into something like an infinite loop if you forget the base case
May end up exceeding time and memory limits on Prutor
Will get a TLE/runtime error message on Prutor
Careful: problems that can be solved using recursion can
always be solved using loops too
Fundamental result in computer science: Church-Turing thesis
Disadvantage
: loop solutions sometimes very difficult to write and read
Advantage
: loop solutions can be much faster (at least in compiled
languages like C) than the recursion solution
4
fac(n) = n*fac(n-1);
Recognizing Recursion
Sometimes it is very easy to see that the problem can be
solved using recursion – example factorial, Fibonacci
Sometimes it is harder to see that recursion can be used to
solve the problem – example gcd, partition
No small set of golden rules on how to find out when and if
a problem can be solved using recursion
Need to look at the problem carefully and see if it can be
solved using smaller versions of the same problem
Will see some examples of this in ESC101. More examples in
advanced courses e.g. ESO207, CS345
5
Example 1: Factorial
6
int fact(int a){if(a == 0) return 1;
return a * fact(a - 1);
}
int main(){ printf("%d", fact(1+1));}
2
2
1
1
0
0
1
1
2
2
2
1
1
Example 1: Factorial
int fact(int a){if(a == 0) return 1;
return a * fact(a - 1);
}
int main(){ printf("%d", fact(2*3));}
720
= 1
= 6 * fact(5)
= 5 * fact(4)
= 4 * fact(3)
= 3 * fact(2)
= 2 * fact(1)
= 1 * fact(0)
1 = 1
1 = 2
2 = 6
6 = 24
24 = 120
120 = 720
See how many
clones got created!
Creating each clone
takes time and memory
This is why recursive
programs can be a bit
slower – be careful
Factorial: The Flow
8
long int factorial(int n){if(n==0)
return 1;
else
return(n*factorial(n-1));
}
F(5)
main()
F(4)
F(3)
F(2)
F(1)
F(0)
F(5)
F(4)
F(3)
F(2)
F(1)
main()
1
2
6
24
120
1
Values returned in
reverse order
Example 2: Fibonacci Numbers
There are two base cases for Fibonacci numbers
The first Fibonacci number is defined to be 0
The second Fibonacci number is defined to be 1
Recursive case: for n > 2, n-th Fibonacci number is the sum
of the previous two Fibonacci numbers
9
int fib(int n){if(n == 1) return 0;
if(n == 2) return 1;
return fib(n-1) + fib(n-2);
}
int main(){ printf("%d", fib(5));}
Explosion
of clones!
Wasted effort too!
fib(1) calculated twice
fib(2) calculated 3 times
fib(3) calculated twice
I
m
a
g
i
n
e
t
h
e
n
u
m
b
e
r
o
f
c
l
o
n
e
s
t
o
c
a
l
c
u
l
a
t
e
f
i
b
(
1
0
0
)
.
C
h
a
l
l
e
n
g
e
:
d
o
n
’
t
i
m
a
g
i
n
e
–
f
i
n
d
o
u
t
I could have easily solved
this problem using a for loop
– much faster and no clones
That’s why we were warned.
Recursion allows neat code but
sometimes can be slower
Attack of the Clones
10
fib(1) calculated 3 times
fib(2) calculated 5 times
fib(3) calculated 3 times
fib(4) calculated 2 times
Recursion vs Iteration
11
The recursive program is
closer to the definition
and easier to read.
But very very
inefficient
W
r
i
t
e
a
f
u
n
c
t
i
o
n
t
o
c
o
m
p
u
t
e
t
h
e
n
-
t
h
F
i
b
o
n
a
c
c
i
n
u
m
b
e
r
Space complexity of recursion
Every time a recursive function makes a call to itself
Another call to the function is placed in program memory
This memory space can no longer be allocated elsewhere
The amount of memory needed to execute a program is
called its space complexity
Iterative programs’ space complexity is relatively easy to
analyse
It does not change as a function of the inputs (mostly)
Not so for recursive programs
Space complexity is a function of the maximum depth of the recursion that will be
needed
Is input-dependent
Have to be careful about memory limitations when using recursive algorithms
12
Greatest common divisor
Sometimes recursion can make code faster too
One of the fastest algorithms for computing gcd is called
the
Euclid’s algorithm
and it
defines gcd recursively
!
Note that since a % b is always less than b, this indeed
defines gcd in terms of gcd on “smaller” inputs
What is the base case here?
When b divides a i.e. when a % b = 0, then we have gcd(a, b) = b
13
GCD using Recursion
14
int gcd(int a, int b){if(a < b)
return gcd(b, a);
if(a % b == 0)
return b;
return gcd(b, a % b);
}
The base case
Convince yourself that this will work by calculating some of the outputs by hand.
Partitions
15
Partitions of a number are the different ways in which we
can write the number as a sum of smaller numbers
For example, the partitions of 4 are
1 + 1 + 1 + 1
1 + 1 + 2
1 + 3
2 + 2
4
We can generate partitions of n using partitions of n-1
Need to be a bit careful to ensure that we do not repeat partitions i.e. we
do not write both 1 + 3 and 3 + 1 since they are the same partition
Note that these are
all the partitions of 3
Easy way of ensuring this – make sure
that numbers are writing in increasing
order so that 3 + 1 is disqualified
Code for partitioning
16
v
o
i
d
p
a
r
t
i
t
i
o
n
(
c
h
a
r
*
s
t
r
,
i
n
t
n
,
i
n
t
n
e
x
t
,
i
n
t
m
i
n
)
{i
f
(
n
=
=
0
)
{s
t
r
[
n
e
x
t
]
=
'
\
0
'
;
p
r
i
n
t
f
(
"
%
s
\
n
"
,
s
t
r
)
;
r
e
t
u
r
n
;
}
i
n
t
i
;
i
f
(
n
e
x
t
)
s
t
r
[
n
e
x
t
+
+
]
=
'
+
'
;
f
o
r
(
i
=
m
i
n
;
i
<
=
n
;
i
+
+
)
{s
t
r
[
n
e
x
t
]
=
'
0
'
+
i
;
p
a
r
t
i
t
i
o
n
(
s
t
r
,
n
-
i
,
n
e
x
t
+
1
,
i
)
;
}
}
Base case is to terminate the
string of numbers and print it
Print ‘+’ after each number
In increasing order, to avoid
repeats
Dig down into the recursion well until n-i becomes 0, at which point the
base case will return
p
a
r
t
i
t
i
o
n
(
s
t
r
,
4
,
0
,
1
)
O
u
t
p
u
t
:
1+1+1+1
1+1+2
1+3
2+2
4
Base case returns
Discover the fascinating realm of recursion in computing, where problems are solved through smaller versions of themselves. Dive into concepts like mutual recursion, elegant code writing, and recognizing recursion's power. Learn about the advantages and challenges recursion presents, and explore its fundamental role in computer science. Delve into examples like factorials, Fibonacci sequences, and more. Understand how recursion offers elegant solutions and when to use it effectively.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Recursion ESC101: Fundamentals of Computing Nisheeth
Recursion Process of solving a problem using solutions to smaller versions of the same problem! You have already encountered recursion in mathematics Factorial function is defined in terms of factorial itself! Proof by induction is basically a recursive proof Claim: 1 + 2 + 3 + + n = n(n+1)/2 Proof: Base case: for n = 1 true by inspection Inductive case: (1 + + n) = (1 + + n-1) + n = (n-1)n/2 + n = n(n+1)/2 Notice that we need a base case and recursive case In case of factorial, fac(0) was the base case. This is true when writing recursive functions in C language as well We used the proof for the case n-1 to prove the case n ESC101: Fundamentals of Computing
Mutual Recursion Two functions calling each other in a recursive fashion Even(n) = (n == 0) || Odd(n-1) Odd(n) = (n != 0) && Even(n-1) Note: The above example is not the most efficient way to check if a number of even or add but just an illustration of mutual recursion ESC101: Fundamentals of Computing
About Recursion Recursion can allow us to write very elegant code Very easy to understand what is going on by just reading function definition Sometimes you can just copy the function definition into code Careful: do not forget to write down the base case Will go into something like an infinite loop if you forget the base case May end up exceeding time and memory limits on Prutor Will get a TLE/runtime error message on Prutor Careful: problems that can be solved using recursion can always be solved using loops too Fundamental result in computer science: Church-Turing thesis Disadvantage: loop solutions sometimes very difficult to write and read Advantage: loop solutions can be much faster (at least in compiled languages like C) than the recursion solution fac(n) = n*fac(n-1); ESC101: Fundamentals of Computing
Recognizing Recursion Sometimes it is very easy to see that the problem can be solved using recursion example factorial, Fibonacci Sometimes it is harder to see that recursion can be used to solve the problem example gcd, partition No small set of golden rules on how to find out when and if a problem can be solved using recursion Need to look at the problem carefully and see if it can be solved using smaller versions of the same problem Will see some examples of this in ESC101. More examples in advanced courses e.g. ESO207, CS345 ESC101: Fundamentals of Computing
Example 1: Factorial int fact(int a){ if(a == 0) return 1; return a * fact(a - 1); } int main(){ printf("%d", fact(1+1)); } 1 1 fact() a 0 0 1 1 fact() a 2 main() 2 2 1 1 fact() 2 2 a ESC101: Fundamentals of Computing
Example 1: Factorial int fact(int a){ if(a == 0) return 1; return a * fact(a - 1); } int main(){ printf("%d", fact(2*3)); } See how many clones got created! Creating each clone takes time and memory This is why recursive programs can be a bit slower be careful fact(0) = 1 fact(1) fact(2) fact(3) = 1 * fact(0) 1 = 1 = 2 * fact(1) 1 = 2 = 3 * fact(2) 2 = 6 720 main() fact(6) = 6 * fact(5) 120 = 720 fact(5) = 5 * fact(4) 24 = 120 fact(4) ESC101: Fundamentals of Computing = 4 * fact(3) 6 = 24
Factorial: The Flow long int factorial(int n){ if(n==0) return 1; else return(n*factorial(n-1)); } main() main() 120 F(5) F(5) 24 F(4) F(4) 6 F(3) F(3) 2 F(2) 1 F(2) F(1) F(1) 1 Values returned in reverse order F(0) ESC101: Fundamentals of Computing
Example 2: Fibonacci Numbers There are two base cases for Fibonacci numbers The first Fibonacci number is defined to be 0 The second Fibonacci number is defined to be 1 Recursive case: for n > 2, n-th Fibonacci number is the sum of the previous two Fibonacci numbers int fib(int n){ if(n == 1) return 0; if(n == 2) return 1; return fib(n-1) + fib(n-2); } int main(){ printf("%d", fib(5)); } Imagine the number of clones to calculate fib(100). Challenge: don t imagine find out Explosion of clones! Wasted effort too! fib(1) calculated twice fib(2) calculated 3 times fib(3) calculated twice That s why we were warned. Recursion allows neat code but sometimes can be slower I could have easily solved this problem using a for loop much faster and no clones fib(5) fib(3) fib(4) fib(2) fib(3) fib(1) fib(2) fib(1) fib(2) ESC101: Fundamentals of Computing
Attack of the Clones fib(1) calculated 3 times fib(2) calculated 5 times fib(3) calculated 3 times fib(4) calculated 2 times fib(6) fib(4) fib(5) fib(3) fib(2) fib(4) fib(3) fib(2) fib(1) fib(3) fib(2) fib(2) fib(1) fib(2) fib(1) ESC101: Fundamentals of Computing
Recursion vs Iteration Write a function to compute Write a function to compute the n the n- -th th Fibonacci number Fibonacci number The recursive program is closer to the definition and easier to read. int fib(int n) { int first = 0, second = 1; int next, c; if (n <= 1) return n; for ( c = 1; c < n ; c++ ) { next = first + second; first = second; second = next; } return next; } But very very inefficient int fib(int n) { if ( n <= 1 ) return n; else return fib(n-1) + fib(n-2); } ESC101: Fundamentals of Computing
Space complexity of recursion Every time a recursive function makes a call to itself Another call to the function is placed in program memory This memory space can no longer be allocated elsewhere The amount of memory needed to execute a program is called its space complexity Iterative programs space complexity is relatively easy to analyse It does not change as a function of the inputs (mostly) Not so for recursive programs Space complexity is a function of the maximum depth of the recursion that will be needed Is input-dependent Have to be careful about memory limitations when using recursive algorithms ESC101: Fundamentals of Computing
Greatest common divisor Sometimes recursion can make code faster too One of the fastest algorithms for computing gcd is called the Euclid s algorithm and it defines gcd recursively! Note that since a % b is always less than b, this indeed defines gcd in terms of gcd on smaller inputs What is the base case here? When b divides a i.e. when a % b = 0, then we have gcd(a, b) = b ESC101: Fundamentals of Computing
GCD using Recursion int gcd(int a, int b){ if(a < b) return gcd(b, a); if(a % b == 0) return b; return gcd(b, a % b); } The base case Convince yourself that this will work by calculating some of the outputs by hand. ESC101: Fundamentals of Computing
Partitions Partitions of a number are the different ways in which we can write the number as a sum of smaller numbers For example, the partitions of 4 are 1 + 1 + 1 + 1 1 + 1 + 2 1 + 3 2 + 2 4 We can generate partitions of n using partitions of n-1 Need to be a bit careful to ensure that we do not repeat partitions i.e. we do not write both 1 + 3 and 3 + 1 since they are the same partition Note that these are all the partitions of 3 Easy way of ensuring this make sure that numbers are writing in increasing order so that 3 + 1 is disqualified ESC101: Fundamentals of Computing
Code for partitioning void partition(char * void partition(char *str if(n == 0){ if(n == 0){ str printf return; } int int i i; ; if(next) if(next) str for( for(i i = min; str partition( } } } } str, , int int n, n, int int next, next, int int min){ min){ Base case is to terminate the string of numbers and print it str[next] = ' [next] = '\ \0'; printf("%s ("%s\ \n", return; } 0'; n", str str); ); partition( partition(str Output: Output: 1+1+1+1 1+1+2 1+3 2+2 4 str, 4, 0, 1) , 4, 0, 1) Base case returns Print + after each number str[next++] = '+'; [next++] = '+'; = min; i i <= n; <= n; i i++){ str[next] = '0' + [next] = '0' + i i; ; partition(str ++){ In increasing order, to avoid repeats str, n , n - - i i, next + 1, , next + 1, i i); ); Dig down into the recursion well until n-i becomes 0, at which point the base case will return ESC101: Fundamentals of Computing
