BITS Pilani

K K Birla Goa Campus

CSF111: Computer Programming

Recursion III – How it works

Swaroop Joshi

2023 These slides borrow a lot from CSE2221 at OSU

The questions
considered before

✤ How to think about recursion so

you can use it to develop elegant
solutions

✤ Why do recursive functions work

The questions Answer: Pretend there is a FreeLunch
Library with a function that has the same

considered before contract as the code you’re trying to write

(but it works only for smaller problems)

✤ How to think about recursion so

you can use it to develop elegant
solutions

✤ Why do recursive functions work

The questions
considered before

✤ How to think about recursion so

you can use it to develop elegant
solutions

✤ Why do recursive functions work

Con dence building method based

on mathematical induction
fi
The questions
considered before

✤ How to think about recursion so The question considered

you can use it to develop elegant
solutions only later now
✤ Why do recursive functions work
The questions
considered before

✤ How to think about recursion so The question considered

you can use it to develop elegant
solutions only later now
✤ How do recursive functions work
✤ Why do recursive functions work
The questions
considered before

✤ How to think about recursion so The question considered

you can use it to develop elegant
solutions only later now
✤ How do recursive functions work
✤ Why do recursive functions work

Caution! If you insist on thinking

about recursions this way, you may
never be fully capable of
developing elegant recursive
solutions!
Recursion – a familiar example

/**
* @brief Computes n! for the given n.
* Requires n >= 0
*/ int main() {
int factorial(int n) { int n = 3;
int answer = 1; int answer = factorial(n);
if (n > 0) { printf("%d! = %d\n", n, answer);
answer = n * factorial(n - 1);
}
return 0;
return answer;
}
}
 Program State

n = 3

int answer = 1;

n =
answer =
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =

n =
answer =

return answer;
 Program State

n = 3

int answer = 1;

n = 3
answer =
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =

n =
answer =

return answer;
 Program State

n = 3

int answer = 1;

n = 3
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =

n =
answer =

return answer;
 Program State

n = 3

int answer = 1;

n = 3
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n = 3
answer =

n =
answer =

return answer;
 Program State

n = 3

int answer = 1;

n = 3
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n = 3
answer = 6

n =
answer =

return answer;
 Program State

n = 3

int answer = 1;

n = 3
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n = 3
answer = 6

n = 3
answer =

return answer;
 Program State

n = 3

int answer = 1;

n = 3
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n = 3
answer = 6

n = 3
answer = 6

return answer;
 Program State

n = 3

int answer = 1;

n = 3
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n = 3
answer = 6

n = 3
answer = 6

return answer;
 Program State

n = 3

int answer = 1;

n = 3
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n = 3
answer = 6

} How does this recursive

call work? n = 3
answer = 6

return answer;
 Program State

n = 3

int answer = 1;

n = 3
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n = 3
answer = 6

} How does this recursive

call work? n = 3
answer = 6

return answer; Answer: Like any other

function call, e.g., printf!
How every call works

✤ First, the tracing table for the code making the call is suspended and that
tracing table is pushed onto the runtime stack

✤ The runtime stack, often called simply “the stack”, is effectively just a
stack of tracing tables, each partially lled in with the results of the code
in that tracing table as executed so far
fi
How every call works

✤ A new tracing table is created, containing the code for the function body
being called

✤ The argument values are copied from the suspended tracing table into the
parameters to start the new tracing table

✤ Execution in the new tracing table continues until it calls a function…

Let’s start from main

Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
Let’s start from main

Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
This tracing table executes till
here, and then …
The partial tracing table
for main is pushed on
the stack…

Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 A new tracing table for
Program (factorial) State the called function is
created with the passed
n = 3 parameter as the starting
value
int answer = 1;

n =
answer =
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =

n =
answer =

return answer; Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 3

int answer = 1;

n =3
answer =
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =

n =
answer =

return answer; Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 3

int answer = 1;

n =3
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =

n =
answer =

return answer; Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 3

int answer = 1;

n =3
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =

} This tracing table

continues till a function n =
is called… answer =

return answer; Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
The partial tracing table
for factorial(3) is pushed
on the stack…

Program (factorial) State

n = 3
int answer = 1;
n = 2
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =
}
n =
answer =
return answer;

Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 A new tracing table for
Program (factorial) State the called function is
created with the passed
n = 2 parameter as the starting
value
int answer = 1;

n =
answer =
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer = Program (factorial) State
n = 3

}
int answer = 1;
n = 2
answer = 1
if (n > 0) {

n =
answer = n * factorial(n - 1);
n =
answer =

answer = }
n =
answer =

return answer;
return answer;

Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 2

int answer = 1;

n =2
answer =
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer = Program (factorial) State
n = 3

}
int answer = 1;
n = 2
answer = 1
if (n > 0) {

n =
answer = n * factorial(n - 1);
n =
answer =

answer = }
n =
answer =

return answer;
return answer;

Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 2

int answer = 1;

n =2
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer = Program (factorial) State
n = 3

}
int answer = 1;
n = 2
answer = 1
if (n > 0) {

n =
answer = n * factorial(n - 1);
n =
answer =

answer = }
n =
answer =

return answer;
return answer;

Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 2

int answer = 1;

n =2
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer = Program (factorial) State
n = 3

}
int answer = 1;

This tracing table n = 2

answer = 1
if (n > 0) {

continues till a function n =

answer = n * factorial(n - 1);
n =
answer =

is called… answer = }
n =
answer =

return answer;
return answer;

Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State
n = 3
int answer = 1;
n =
answer =
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =
}
n =
answer =
return answer;
Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
The partial tracing table Program (factorial) State

for factorial(2) is pushed int answer = 1;

n = 2

n = 2
on the stack… if (n > 0) {
answer = 1

answer = n * factorial(n - 1);

n =
answer =
}
n =
answer =
return answer;
Program (factorial) State
n = 3
int answer = 1;
n =
answer =
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =
}
n =
answer =
return answer;
Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 A new tracing table for
Program (factorial) State the called function is
created with the passed
n = 1 parameter as the starting
value
int answer = 1;

n = Program (factorial)
n = 2
State

answer = int answer = 1;

n = 2
answer = 1
if (n > 0) { if (n > 0) {
answer = n * factorial(n - 1);

answer = n * factorial(n - 1); n =

answer =
}
n = n =
answer =

answer = return answer;

Program (factorial) State
n = 3

} int answer = 1;
n =
answer =
if (n > 0) {

n = answer = n * factorial(n - 1);

n =

answer =
answer =
}
n =
answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 1

int answer = 1;

n =1 Program (factorial)
n = 2
State

answer = int answer = 1;

n = 2
answer = 1
if (n > 0) { if (n > 0) {
answer = n * factorial(n - 1);

answer = n * factorial(n - 1); n =

answer =
}
n = n =
answer =

answer = return answer;

Program (factorial) State
n = 3

} int answer = 1;
n =
answer =
if (n > 0) {

n = answer = n * factorial(n - 1);

n =

answer =
answer =
}
n =
answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 1

int answer = 1;

n =1 Program (factorial)
n = 2
State

answer = 1 int answer = 1;

n = 2
answer = 1
if (n > 0) { if (n > 0) {
answer = n * factorial(n - 1);

answer = n * factorial(n - 1); n =

answer =
}
n = n =
answer =

answer = return answer;

Program (factorial) State
n = 3

} int answer = 1;
n =
answer =
if (n > 0) {

n = answer = n * factorial(n - 1);

n =

answer =
answer =
}
n =
answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 1

int answer = 1;

n =1 Program (factorial)
n = 2
State

answer = 1 int answer = 1;

n = 2
answer = 1
if (n > 0) { if (n > 0) {
answer = n * factorial(n - 1);

answer = n * factorial(n - 1); n =

answer =
}
n = n =
answer =

answer = return answer;

Program (factorial) State
n = 3

} This tracing table

int answer = 1;
n =
answer =
if (n > 0) {

continues till a function n = answer = n * factorial(n - 1);

n =

answer =
answer =

is called… }
n =
answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State
n = 2
int answer = 1;
n = 2
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =
}
n =
answer =
return answer;
Program (factorial) State
n = 3
int answer = 1;
n =
answer =
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =
}
n =
answer =
return answer;
Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State
n = 1
int answer = 1;
n = 1
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =

The partial tracing table }

n =

for factorial(1) is pushed

answer =
return answer;

Program (factorial) State

on the stack… int answer = 1;

n = 2

n = 2
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =
}
n =
answer =
return answer;
Program (factorial) State
n = 3
int answer = 1;
n =
answer =
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =
}
n =
answer =
return answer;
Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 A new tracing table for
Program (factorial) State the called function is
Program (factorial)
n = 1
State

created with the passed

int answer = 1;
n = 1

n = 0
answer = 1

parameter as the starting

if (n > 0) {
answer = n * factorial(n - 1);
n =

value answer =

int answer = 1;
}
n =
answer =
return answer;

n = Program (factorial)
n = 2
State

answer = int answer = 1;

n = 2
answer = 1
if (n > 0) { if (n > 0) {
answer = n * factorial(n - 1);

answer = n * factorial(n - 1); n =

answer =
}
n = n =
answer =

answer = return answer;

Program (factorial) State
n = 3

} int answer = 1;
n =
answer =
if (n > 0) {

n = answer = n * factorial(n - 1);

n =

answer =
answer =
}
n =
answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State Program (factorial)
n = 1
State

int answer = 1;
n = 1

n = 0
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =

int answer = 1;
}
n =
answer =
return answer;

n =0 Program (factorial)
n = 2
State

answer = int answer = 1;

n = 2
answer = 1
if (n > 0) { if (n > 0) {
answer = n * factorial(n - 1);

answer = n * factorial(n - 1); n =

answer =
}
n = n =
answer =

answer = return answer;

Program (factorial) State
n = 3

} int answer = 1;
n =
answer =
if (n > 0) {

n = answer = n * factorial(n - 1);

n =

answer =
answer =
}
n =
answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State Program (factorial)
n = 1
State

int answer = 1;
n = 1

n = 0
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =

int answer = 1;
}
n =
answer =
return answer;

n =0 Program (factorial)
n = 2
State

answer = 1 int answer = 1;

n = 2
answer = 1
if (n > 0) { if (n > 0) {
answer = n * factorial(n - 1);

answer = n * factorial(n - 1); n =

answer =
}
n = n =
answer =

answer = return answer;

Program (factorial) State
n = 3

} int answer = 1;
n =
answer =
if (n > 0) {

n = answer = n * factorial(n - 1);

n =

answer =
answer =
}
n =
answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State Program (factorial)
n = 1
State

int answer = 1;
n = 1

n = 0
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =

int answer = 1;
}
n =
answer =
return answer;

n =0 Program (factorial)
n = 2
State

answer = 1 int answer = 1;

n = 2
answer = 1
if (n > 0) { if (n > 0) {
answer = n * factorial(n - 1);

answer = n * factorial(n - 1); n =

answer =
}
n =- n =
answer =

answer = return answer;

Program (factorial) State
n = 3

} int answer = 1;
n =
answer =
if (n > 0) {

n = answer = n * factorial(n - 1);

n =

answer =
answer =
}
n =
answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State Program (factorial)
n = 1
State

int answer = 1;
n = 1

n = 0
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =

int answer = 1;
}
n =
answer =
return answer;

n =0 Program (factorial)
n = 2
State

answer = 1 int answer = 1;

n = 2
answer = 1
if (n > 0) { if (n > 0) {
answer = n * factorial(n - 1);

answer = n * factorial(n - 1); n =

answer =
}
n =- n =
answer =

answer = - return answer;

Program (factorial) State
n = 3

} int answer = 1;
n =
answer =
if (n > 0) {

n = answer = n * factorial(n - 1);

n =

answer =
answer =
}
n =
answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State Program (factorial)
n = 1
State

int answer = 1;
n = 1

n = 0
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =

int answer = 1;
}
n =
answer =
return answer;

n =0 Program (factorial)
n = 2
State

answer = 1 int answer = 1;

n = 2
answer = 1
if (n > 0) { if (n > 0) {
answer = n * factorial(n - 1);

answer = n * factorial(n - 1); n =

answer =
}
n =- n =
answer =

answer = - return answer;

Program (factorial) State
n = 3

} int answer = 1;
n =
answer =

=0
if (n > 0) {

n answer = n * factorial(n - 1);

n =

answer =
answer =
}
n =
answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State Program (factorial)
n = 1
State

int answer = 1;
n = 1

n = 0
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =

int answer = 1;
}
n =
answer =
return answer;

n =0 Program (factorial)
n = 2
State

answer = 1 int answer = 1;

When this function returns, the n = 2

answer = 1
if (n > 0) { if (n > 0) {

partial tracing table from the

answer = n * factorial(n - 1);top answer = n * factorial(n - 1);
n =
answer =

of the stack is brought back… n =-

}
n =
answer =

answer = - return answer;

Program (factorial) State
n = 3

} int answer = 1;
n =
answer =

=0
if (n > 0) {

n answer = n * factorial(n - 1);

n =

answer = 1
answer =
}
n =
answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 1

int answer = 1;

n =1 Program (factorial)
n = 2
State

answer = 1 int answer = 1;

n = 2
answer = 1
if (n > 0) { if (n > 0) {
answer = n * factorial(n - 1);

answer = n * factorial(n - 1); n =

answer =
}
n = n =
answer =

answer = return answer;

Program (factorial) State
n = 3

} int answer = 1;
n =
answer =
if (n > 0) {

n = answer = n * factorial(n - 1);

n =

answer =
answer =
}
n =
answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 The tracing table for
Program (factorial) State factorial(1) is brought back
from the top of the stack.
n = 1

int answer = 1;

n =1 Program (factorial)
n = 2
State

answer = 1 int answer = 1;

n = 2
answer = 1
if (n > 0) { if (n > 0) {
answer = n * factorial(n - 1);

answer = n * factorial(n - 1); n =

answer =
}
n = n =
answer =

answer = return answer;

Program (factorial) State
n = 3

} int answer = 1;
n =
answer =
if (n > 0) {

n = answer = n * factorial(n - 1);

n =

answer =
answer =
}
n =
answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 1

int answer = 1;

n =1 Program (factorial)
n = 2
State

answer = 1 int answer = 1;

n = 2
answer = 1
if (n > 0) { if (n > 0) {
answer = n * factorial(n - 1);

answer = n * factorial(n - 1); n =

answer =
}
n = n =
answer =

answer = return answer;

Program (factorial) State

Continue tracing by replacing

n = 3

} int answer = 1;
n =

the function call factorial(n-1) if (n > 0) {

answer =

n = answer = n * factorial(n - 1);

with the return value from the answer = n =

answer =
}

previous tracing table n =

answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 1

int answer = 1;

n =1 Program (factorial)
n = 2
State

answer = 1 int answer = 1;

n = 2
answer = 1
if (n > 0) { if (n > 0) {
answer = n * factorial(n - 1);

answer = n * factorial(n - 1); n =

answer =

=1
}
n n =
answer =

answer = 1 return answer;

Program (factorial) State
n = 3

} int answer = 1;
n =
answer =
if (n > 0) {

n = answer = n * factorial(n - 1);

n =

answer =
answer =
}
n =
answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 1

int answer = 1;

n =1 Program (factorial)
n = 2
State

answer = 1 int answer = 1;

n = 2
answer = 1
if (n > 0) { if (n > 0) {
answer = n * factorial(n - 1);

answer = n * factorial(n - 1); n =

answer =

=1
}
n n =
answer =

answer = 1 return answer;

Program (factorial) State
n = 3

} int answer = 1;
n =
answer =
if (n > 0) {

n =1 answer = n * factorial(n - 1);

n =

answer = 1
answer =
}
n =
answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 2

int answer = 1;

n =2
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer = Program (factorial) State
n = 3

} int answer = 1;
n =
answer =
if (n > 0) {

n = answer = n * factorial(n - 1);

n =

answer =
answer =
}
n =
answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 The tracing table for
Program (factorial) State factorial(2) is brought back
from the top of the stack.
n = 2

int answer = 1;

n =2
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer = Program (factorial) State
n = 3

} int answer = 1;
n =
answer =
if (n > 0) {

n = answer = n * factorial(n - 1);

n =

answer =
answer =
}
n =
answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 2

int answer = 1;

n =2
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer = Program (factorial) State

Continue tracing by replacing

n = 3

} int answer = 1;
n =

the function call factorial(n-1) if (n > 0) {

answer =

n = answer = n * factorial(n - 1);

with the return value from the answer = n =

answer =
}

previous tracing table n =

answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 2

int answer = 1;

n =2
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =2
answer = 2 Program (factorial) State
n = 3

} int answer = 1;
n =
answer =
if (n > 0) {

n = answer = n * factorial(n - 1);

n =

answer =
answer =
}
n =
answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 2

int answer = 1;

n =2
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =2
answer = 2 Program (factorial) State
n = 3

} int answer = 1;
n =
answer =
if (n > 0) {

n =2 answer = n * factorial(n - 1);

n =

answer = 2
answer =
}
n =
answer =

return answer; return answer;

Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 3

int answer = 1;

n =3
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =

n =
answer =

return answer; Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 The tracing table for
Program (factorial) State factorial(2) is brought back
from the top of the stack.
n = 3

int answer = 1;

n =3
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =

n =
answer =

return answer; Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 3

int answer = 1;

n =3
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =
answer =

} Continue tracing by replacing

the function call factorial(n-1)
n =
with the return value from the answer =
previous tracing table
return answer; Program (main) State
int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 3

int answer = 1;

n =3
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =3
answer = 2

n =
answer =

return answer; Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
 Program (factorial) State

n = 3

int answer = 1;

n =3
answer = 1
if (n > 0) {
answer = n * factorial(n - 1);
n =3
answer = 2

n =3
answer = 6

return answer; Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
… and we are back at main

Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n =
answer =
printf("%d! = %d\n", n, answer);
… and we are back at main

Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n =
And the result is re ected in
answer = the calling position…
printf("%d! = %d\n", n, answer);
fl
… and we are back at main

Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n = 3
And the result is re ected in
answer = the calling position…
printf("%d! = %d\n", n, answer);
fl
… and we are back at main

Program (main) State

int n = 3;
n = 3
int answer = factorial(n);
n = 3
And the result is re ected in
answer = 6 the calling position…
printf("%d! = %d\n", n, answer);
fl
Conclusion
Conclusion

✤ Each call to a function—whether recursive or not—effectively results in the

creation of a new tracing table containing the body of the called function
Conclusion

✤ Each call to a function—whether recursive or not—effectively results in the

creation of a new tracing table containing the body of the called function

✤ Each tracing table has its own variables

✤ Its own formal parameters

✤ Its own local variables

Conclusion
Conclusion

✤ This was just to show you how function calls work so you know how
recursion works
Conclusion

✤ This was just to show you how function calls work so you know how
recursion works

✤ But this is not how you should think about writing elegant recursive
solutions …
Conclusion

✤ This was just to show you how function calls work so you know how
recursion works

✤ But this is not how you should think about writing elegant recursive
solutions …

✤ … unless you really want to mentally execute this kind of a series of

events to check your thinking!