Recursion in Programming
Module 4 - Part 2
Recursion
F
a
c
t
o
r
i
a
l
!
6! = 6*5*4*3*2*1
F
a
c
t
o
r
i
a
l
!
75! = ???
F
a
c
t
o
r
i
a
l
!
75! = 75*74!
F
a
c
t
o
r
i
a
l
!
75! = 75*74!
Defined in terms of itself
F
a
c
t
o
r
i
a
l
!
75! = 75*74!
To solve this problem, we need to figure out 74!
F
a
c
t
o
r
i
a
l
!
75! = 75*74!
To solve this problem, we need to figure out 73!
74! = 74*73!
F
a
c
t
o
r
i
a
l
!
75! = 75*74!
To solve this problem, we need to figure out 72!
74! = 74*73!
73! = 73*72!
When would it stop?
F
a
c
t
o
r
i
a
l
!
n! = n*(n-1)!
In general…
R
e
c
u
r
s
i
o
n
•
When a method calls itself
•
Easy to identify
•
Going to create “clones” of the function
•
Usually, the clone has a
smaller
problem to work
•
Requirements
•
Must have the recursive call
•
Must have a terminating condition
•
Must make progress towards terminating
R
e
c
u
r
s
i
o
n
•
A recursive method works like this:
•
If it’s asked the simplest problem, it directly
solves it. This is called the base condition/base
case.
•
If it’s asked a more complex question it breaks
that question into a slightly more simple problem
and makes a recursive call to solve the simpler
problem.
•
Eventually
R
e
c
u
r
s
i
v
e
T
e
c
h
n
i
q
u
e
D
e
s
i
g
n
•
First: Determine the base case, i.e. the
stopping point for the recursion. It should
normally be the simplest case.
•
Second: What is the case that is just one
step above it? Can it be generalized
enough to fit?
R
e
c
u
r
s
i
v
e
F
a
c
t
o
r
i
a
l
C
a
l
c
u
l
a
t
i
o
n
s
•
A recursive declaration of the factorial
method is arrived at by observing the
following relationship:
n
! =
n
.
(
n
– 1)!
•
What is the simplest case/ terminating
state?
you could use either 0! =1 or 1!=1
•
so …
b
a
s
e
c
a
s
e
/
s
t
o
p
p
i
n
g
s
t
a
t
e
public int
factorial(
int
n)
{if
(n==1)
return
1;
…
W
h
a
t
i
f
n
=
=
2
?
•
2! = 2 *1!
•
which leads to the rest of the code:
return
n * factorial(n-1);
A
r
e
c
u
r
s
i
v
e
f
a
c
t
o
r
i
a
l
m
e
t
h
o
d
public int
factorial(
int
n)
{if
(n==1)
return
1;
return
n* factorial(n-1);
}
Let’s trace it!
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
function stack
main
f = factorial(4)
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
fact(4)
n == 4
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
n == 4
fact(4)
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
n == 4
fact(4)
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
n == 4
fact(4)
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
n == 4
fact(4)
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
n == 4
result = 4 * factorial(3)
fact(4)
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
n == 4
result = 4 * factorial(3)
fact(4)
Pending Work!
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
n == 3
result = 4 * factorial(3)
fact(4)
fact(3)
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
3
n == 3
result = 4 * factorial(3)
fact(4)
fact(3)
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
3
n == 3
result = 4 * factorial(3)
fact(4)
fact(3)
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
3
n == 3
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * factorial(2)
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
3
n == 3
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * factorial(2)
Pending Work!
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
3
n == 2
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * factorial(2)
fact(2)
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
3
2
n == 2
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * factorial(2)
fact(2)
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
3
2
n == 2
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * factorial(2)
fact(2)
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
3
2
n == 2
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * factorial(2)
fact(2)
result = 2 * factorial(1)
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
3
2
n == 2
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * factorial(2)
fact(2)
result = 2 * factorial(1)
Pending Work!
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
3
2
n == 1
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * factorial(2)
fact(2)
result = 2 * factorial(1)
fact(1)
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
3
2
1
n == 1
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * factorial(2)
fact(2)
result = 2 * factorial(1)
fact(1)
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
3
2
1
n == 1
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * factorial(2)
fact(2)
result = 2 * factorial(1)
fact(1)
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
3
2
1
n == 1
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * factorial(2)
fact(2)
result = 2 * factorial(1)
fact(1)
We “terminated”
return 1
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
3
2
1
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * factorial(2)
fact(2)
result = 2 * factorial(1)
fact(1)
Collapse the stack…
return 1
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
main
f = factorial(4)
Output
4
3
2
1
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * factorial(2)
fact(2)
result = 2 * factorial(1)
fact(1)
return 1
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
Collapse the stack…
main
f = factorial(4)
Output
4
3
2
1
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * factorial(2)
fact(2)
result = 2 * 1
n == 2
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
Collapse the stack…
main
f = factorial(4)
Output
4
3
2
1
2
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * factorial(2)
fact(2)
result = 2 * 1 = 2
n == 2
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
Collapse the stack…
main
f = factorial(4)
Output
4
3
2
1
2
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * factorial(2)
fact(2)
result = 2 * 1 = 2
n == 2
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
Collapse the stack…
main
f = factorial(4)
Output
4
3
2
1
2
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * factorial(2)
fact(2)
result = 2 * 1 = 2
n == 2
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
Collapse the stack…
main
f = factorial(4)
Output
4
3
2
1
2
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * factorial(2)
fact(2)
result = 2 * 1 = 2
n == 2
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
Collapse the stack…
main
f = factorial(4)
Output
4
3
2
1
2
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * 2 = 6
n == 3
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
Collapse the stack…
main
f = factorial(4)
Output
4
3
2
1
2
3
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * 2 = 6
n == 3
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
Collapse the stack…
main
f = factorial(4)
Output
4
3
2
1
2
3
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * 2 = 6
n == 3
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
Collapse the stack…
main
f = factorial(4)
Output
4
3
2
1
2
3
result = 4 * factorial(3)
fact(4)
fact(3)
result = 3 * 2 = 6
n == 3
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
Collapse the stack…
main
f = factorial(4)
Output
4
3
2
1
2
3
result = 4 * 6 = 24
fact(4)
n == 4
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
Collapse the stack…
main
f = factorial(4)
Output
4
3
2
1
2
3
4
result = 4 * 6 = 24
fact(4)
n == 4
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
Collapse the stack…
main
f = factorial(4)
Output
4
3
2
1
2
3
4
result = 4 * 6 = 24
fact(4)
n == 4
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
Collapse the stack…
main
f = factorial(4)
Output
4
3
2
1
2
3
4
result = 4 * 6 = 24
fact(4)
n == 4
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
Collapse the stack…
main
f = 24
Output
4
3
2
1
2
3
4
n == 4
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
Collapse the stack…
main
f = 24
Output
4
3
2
1
2
3
4
24
n == 4
static int
factorial (
int
n) {PRINT(n);
if
(n == 1) {return
1;
}
else
{int
result = n * factorial(n-
1);
PRINT(n);
return
result;
}
}
public void
M/main (S/string[] args)
{int
f = factorial(4);
PRINT(f);
}
Collapse the stack…
C
o
m
m
o
n
P
r
o
g
r
a
m
m
i
n
g
E
r
r
o
r
•
Either omitting the base case or writing
the recursion step incorrectly so that it
does not converge on the base case will
cause infinite recursion, eventually
exhausting memory.
•
T
h
i
s
e
r
r
o
r
i
s
a
n
a
l
o
g
o
u
s
t
o
t
h
e
p
r
o
b
l
e
m
o
f
a
n
i
n
f
i
n
i
t
e
l
o
o
p
i
n
a
n
i
t
e
r
a
t
i
v
e
(
n
o
n
-
r
e
c
u
r
s
i
v
e
)
s
o
l
u
t
i
o
n
.
S
t
a
c
k
O
v
e
r
f
l
o
w
•
Avoid stack overflow. Stack overflow
occurs when you recurse too many times
and run out of memory.
•
Often, it is more efficient to perform
calculations via iteration (looping), but it
can also be easier to express an algorithm
via recursion.
•
Recursion is especially useful for non-
linear situations
C
h
a
l
l
e
n
g
e
•
Write the recursive process for the following:
x^y
•
You may assume that x and y are both
positive integers
x
^
y
s
o
l
u
t
i
o
n
public long
power(
int
x,
int
y)
{if
( y ==1)
return x;
return
x*power(x, y-1);
}
x^y solution with a Java Program
x^y solution with a C# Program
What is generated by PrintNumbers(30)?
public void PrintNumbers(int n)
{if (n > 0
)
{Console.Write(n + " ");
PrintNumbers(n - 1);
Console.Write(n + " ");
}
}
public void PrintNumbers(int n)
{if (n > 0)
{System.out.print(n + " ");
PrintNumbers(n - 1);
System.out.print(n + " ");
}
}
Recursion in programming involves a method calling itself to solve problems by breaking them down into simpler subproblems. The process requires a base condition, recursive calls, and progress towards termination. This technique is illustrated through examples like calculating factorials using recursive functions.
Uploaded on Sep 20, 2024 | 0 Views
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Module 4 - Part 2 Recursion
Factorial! 6! = 6*5*4*3*2*1
Factorial! 75! = ???
Factorial! 75! = 75*74!
Factorial! 75! = 75*74! Defined in terms of itself
Factorial! 75! = 75*74! To solve this problem, we need to figure out 74!
Factorial! 74! = 74*73! 75! = 75*74! To solve this problem, we need to figure out 73!
Factorial! 73! = 73*72! 74! = 74*73! 75! = 75*74! To solve this problem, we need to figure out 72! When would it stop?
Factorial! In general n! = n*(n-1)!
Recursion When a method calls itself Easy to identify Going to create clones of the function Usually, the clone has a smaller problem to work Requirements Must have the recursive call Must have a terminating condition Must make progress towards terminating
Recursion A recursive method works like this: If it s asked the simplest problem, it directly solves it. This is called the base condition/base case. If it s asked a more complex question it breaks that question into a slightly more simple problem and makes a recursive call to solve the simpler problem. Eventually
Recursive Technique Design First: Determine the base case, i.e. the stopping point for the recursion. It should normally be the simplest case. Second: What is the case that is just one step above it? Can it be generalized enough to fit?
Recursive Factorial Calculations A recursive declaration of the factorial method is arrived at by observing the following relationship: n! = n . (n 1)! What is the simplest case/ terminating state? you could use either 0! =1 or 1!=1 so
base case / stopping state public int factorial(int n) { if (n==1) return 1;
What if n == 2? 2! = 2 *1! which leads to the rest of the code: return n * factorial(n-1);
A recursive factorial method public int factorial(int n) { if(n==1) return 1; return n* factorial(n-1); } Let s trace it!
static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); }
static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } function stack public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); }
static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } main f = factorial(4)
n == 4 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } fact(4) main f = factorial(4)
n == 4 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } fact(4) main f = factorial(4)
Output 4 n == 4 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } fact(4) main f = factorial(4)
Output 4 n == 4 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } fact(4) main f = factorial(4)
Output 4 n == 4 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } fact(4) main f = factorial(4)
Output 4 n == 4 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 n == 4 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } Pending Work! public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 n == 3 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(3) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 n == 3 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(3) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 n == 3 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(3) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 n == 3 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(3) result = 3 * factorial(2) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 n == 3 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } Pending Work! fact(3) result = 3 * factorial(2) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 n == 2 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(2) fact(3) result = 3 * factorial(2) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 2 n == 2 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(2) fact(3) result = 3 * factorial(2) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 2 n == 2 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(2) fact(3) result = 3 * factorial(2) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 2 n == 2 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(2) result = 2 * factorial(1) fact(3) result = 3 * factorial(2) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 2 n == 2 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } Pending Work! fact(2) result = 2 * factorial(1) fact(3) result = 3 * factorial(2) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 2 n == 1 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(1) fact(2) result = 2 * factorial(1) fact(3) result = 3 * factorial(2) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 2 1 n == 1 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(1) fact(2) result = 2 * factorial(1) fact(3) result = 3 * factorial(2) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 2 1 n == 1 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(1) fact(2) result = 2 * factorial(1) fact(3) result = 3 * factorial(2) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 2 1 We terminated n == 1 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(1) return 1 fact(2) result = 2 * factorial(1) fact(3) result = 3 * factorial(2) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 2 1 Collapse the stack static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(1) return 1 fact(2) result = 2 * factorial(1) fact(3) result = 3 * factorial(2) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 2 1 Collapse the stack static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(1) return 1 fact(2) result = 2 * factorial(1) fact(3) result = 3 * factorial(2) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 2 1 Collapse the stack n == 2 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(2) result = 2 * 1 fact(3) result = 3 * factorial(2) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 2 1 2 Collapse the stack n == 2 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(2) result = 2 * 1 = 2 fact(3) result = 3 * factorial(2) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 2 1 2 Collapse the stack n == 2 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(2) result = 2 * 1 = 2 fact(3) result = 3 * factorial(2) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 2 1 2 Collapse the stack n == 2 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(2) result = 2 * 1 = 2 fact(3) result = 3 * factorial(2) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 2 1 2 Collapse the stack n == 2 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(2) result = 2 * 1 = 2 fact(3) result = 3 * factorial(2) public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 2 1 2 Collapse the stack n == 3 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(3) result = 3 * 2 = 6 public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 2 1 2 3 Collapse the stack n == 3 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(3) result = 3 * 2 = 6 public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
Output 4 3 2 1 2 3 Collapse the stack n == 3 static int factorial (int n) { PRINT(n); if (n == 1) { return 1; } else { int result = n * factorial(n- 1); PRINT(n); return result; } } fact(3) result = 3 * 2 = 6 public void M/main (S/string[] args) { int f = factorial(4); PRINT(f); } result = 4 * factorial(3) fact(4) main f = factorial(4)
