Data Structures
Lecture 03: Recursion
Edirlei Soares de Lima
Recursive Functions
In programming, a recursive function is a function that calls
itself.
The recursive call can be:
Direct: function A calls itself
Indirect: function A calls a function B which in turn calls A
void myFunction(int n)
{
.
..
myFunction(n-1);
..
Recursion
.
}
Recursive Functions
Recursive function for the factorial calculation:
Base Case
ꢁꢂꢃꢄꢅꢆꢁꢇ ꢈ =1,×=01 , > 0
Recursive Step
Recursive call
int factorial(int n)
{
if (n == 0)
Base Case
return 1;
else
return n * factorial(n-1);
Recursive Step
}
Recursive Functions
Behavior of a recursive function:
When a function is called recursively, a local environment is created
for each call;
Local variables of recursive calls are independent of each other, as if
we were calling different functions.
Recursive Functions
include <stdio.h>
#
int factorial(int n)
{
int f;
if (n == 0)
f = 1;
else
f = n * factorial(n-1);
return f;
}
void Start()
{
int n = 3, r;
r = factorial(n);
Debug.Log("Factorial of " + n + " = " + r);
}
Start
Recursive Functions
include <stdio.h>
#
int factorial(int n)
{
int f;
if (n == 0)
f = 1;
else
f = n * factorial(n-1);
return f;
}
void Start()
{
int n = 3, r;
r = factorial(n);
Debug.Log("Factorial of " + n + " = " + r);
}
Start
Recursive Functions
include <stdio.h>
#
int factorial(int n)
{
int f;
if (n == 0)
f = 1;
else
f = n * factorial(n-1);
return f;
}
void Start()
{
int n = 3, r;
r = factorial(n);
Debug.Log("Factorial of " + n + " = " + r);
}
Start
Recursive Functions
include <stdio.h>
#
int factorial(int n)
{
int f;
if (n == 0)
f = 1;
else
f = n * factorial(n-1);
return f;
}
void Start()
{
int n = 3, r;
r = factorial(n);
Debug.Log("Factorial of " + n + " = " + r);
}
Start
Recursive Functions
include <stdio.h>
#
int factorial(int n)
{
int f;
if (n == 0)
f = 1;
else
f = n * factorial(n-1);
return f;
}
void Start()
{
int n = 3, r;
r = factorial(n);
Debug.Log("Factorial of " + n + " = " + r);
}
Start
Recursive Functions
include <stdio.h>
#
int factorial(int n)
{
int f;
if (n == 0)
f = 1;
else
f = n * factorial(n-1);
return f;
}
void Start()
{
int n = 3, r;
r = factorial(n);
Debug.Log("Factorial of " + n + " = " + r);
}
Start
Recursive Functions
include <stdio.h>
#
int factorial(int n)
{
int f;
if (n == 0)
f = 1;
else
f = n * factorial(n-1);
return f;
}
void Start()
{
int n = 3, r;
r = factorial(n);
Debug.Log("Factorial of " + n + " = " + r);
}
Start
Recursive Functions
include <stdio.h>
#
int factorial(int n)
{
int f;
if (n == 0)
f = 1;
else
f = n * factorial(n-1);
return f;
}
void Start()
{
int n = 3, r;
r = factorial(n);
Debug.Log("Factorial of " + n + " = " + r);
}
Start
Recursive Functions
include <stdio.h>
#
int factorial(int n)
{
int f;
if (n == 0)
f = 1;
else
f = n * factorial(n-1);
return f;
}
void Start()
{
int n = 3, r;
r = factorial(n);
Debug.Log("Factorial of " + n + " = " + r);
}
Start
Assignment Recursion
1
) Implement the recursive function for the exponentiation
operation:
=1, ꢆꢀ ꢈ = 0
ꢉ ×(), ꢆꢀ ꢈ > 0
Base Case
Recursive Step