Scribd
Upload
13 views29 pages

7 Function R

The document explains the concept of recursion in programming, particularly through the example of calculating factorials using a recursive function. It provides a detailed breakdown of how the recursive calls work and the stack trace involved in computing the factorial of a number. Additionally, it introduces the Fibonacci sequence and demonstrates its calculation using recursion.

Uploaded by

martha.amin25
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
13 views29 pages

7 Function R

The document explains the concept of recursion in programming, particularly through the example of calculating factorials using a recursive function. It provides a detailed breakdown of how the recursive calls work and the stack trace involved in computing the factorial of a number. Additionally, it introduces the Fibonacci sequence and demonstrates its calculation using recursion.

Uploaded by

martha.amin25
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Recursion

 The existence of functions makes possible a


programming technique called recursion.

 Recursion involves a function calling itself.


FACTOR
unsigned long factfunc(unsigned long); //declaration
int main()
{
int n;
unsigned long fact;
cout << “Enter an integer: “;
cin >> n;
fact = factfunc(n);
cout << “Factorial of “ << n << “ is “ << fact << endl;
return 0;
}
unsigned long factfunc (unsigned long n)
{
if (n > 1)
return n * factfunc(n-1);
else
return 1;
}
Version Action Return Value
1 Call 5
2 Call 4
3 Call 3
4 Call 2
5 Call 1
5 Return 1
4 Return 2
3 Return 6
2 Return 24
1 Return 120

argument of 5.
Computing Factorial
factorial(0) = 1;
factorial(n) = n*n-1……2*1=n*factorial(n-1);

n! = n * (n-1)!

4
animation

Computing Factorial
factorial(0) = 1;
factorial(n) = n*factorial(n-
1);
factorial(3)

5
animation

Computing Factorial
factorial(0) = 1;
factorial(n) = n*factorial(n-
1);
factorial(3) = 3 * factorial(2)

6
animation

Computing Factorial
factorial(0) = 1;
factorial(n) = n*factorial(n-
1);
factorial(3) = 3 * factorial(2)
= 3 * (2 * factorial(1))

7
animation

Computing Factorial
factorial(0) = 1;
factorial(n) = n*factorial(n-
1);
factorial(3) = 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * ( 2 * (1 * factorial(0)))

8
animation

Computing Factorial
factorial(0) = 1;
factorial(n) = n*factorial(n-
factorial(3) = 3 * factorial(2) 1);

= 3 * (2 * factorial(1))
= 3 * ( 2 * (1 * factorial(0)))
= 3 * ( 2 * ( 1 * 1)))

9
animation

Computing Factorial
factorial(0) = 1;
factorial(n) = n*factorial(n-
1);
factorial(3) = 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * ( 2 * (1 * factorial(0)))
= 3 * ( 2 * ( 1 * 1)))
= 3 * ( 2 * 1)

10
animation

Computing Factorial
factorial(0) = 1;
factorial(n) = n*factorial(n-
1);
factorial(3) = 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * ( 2 * (1 * factorial(0)))
= 3 * ( 2 * ( 1 * 1)))
= 3 * ( 2 * 1)
=3*2

11
animation

Computing Factorial
factorial(0) = 1;
factorial(n) = n*factorial(n-
1);
factorial(3) = 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * ( 2 * (1 * factorial(0)))
= 3 * ( 2 * ( 1 * 1)))
= 3 * ( 2 * 1)
=3*2
=6

12
animation

Trace Recursive factorial


Executes factorial(4)

factorial(4)
Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2
Stack
return 2 * factorial(1)
Step 3: executes factorial(1)
Step 6: return 1
return 1 * factorial(0)
Step 4: executes factorial(0)
Step 5: return 1
return 1 Main method

13
animation

Trace Recursive factorial

factorial(4)
Step 0: executes factorial(4)
Step 9: return 24 Executes factorial(3)
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2 Stack

return 2 * factorial(1)
Step 3: executes factorial(1)
Step 6: return 1
return 1 * factorial(0)
Step 4: executes factorial(0)
Step 5: return 1 Space Required
for factorial(4)
return 1 Main method

14
animation

Trace Recursive factorial

factorial(4) Executes factorial(2)


Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2 Stack

return 2 * factorial(1)
Step 3: executes factorial(1)
Step 6: return 1
return 1 * factorial(0) Space Required
for factorial(3)
Step 4: executes factorial(0)
Step 5: return 1 Space Required
for factorial(4)
return 1 Main method

15
animation

Trace Recursive factorial

factorial(4) Executes factorial(1)


Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2 Stack

return 2 * factorial(1)
Step 3: executes factorial(1)
Step 6: return 1 Space Required
for factorial(2)
return 1 * factorial(0) Space Required
for factorial(3)
Step 4: executes factorial(0)
Step 5: return 1 Space Required
for factorial(4)
return 1 Main method

16
animation

Trace Recursive factorial

factorial(4) Executes factorial(0)


Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2 Stack

return 2 * factorial(1)
Space Required
Step 3: executes factorial(1) for factorial(1)
Step 6: return 1 Space Required
for factorial(2)
return 1 * factorial(0) Space Required
for factorial(3)
Step 4: executes factorial(0)
Step 5: return 1 Space Required
for factorial(4)
return 1 Main method

17
animation

Trace Recursive factorial

factorial(4) returns 1
Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2 Stack

Space Required
return 2 * factorial(1) for factorial(0)
Space Required
Step 3: executes factorial(1) for factorial(1)
Step 6: return 1 Space Required
for factorial(2)
return 1 * factorial(0) Space Required
for factorial(3)
Step 4: executes factorial(0)
Step 5: return 1 Space Required
for factorial(4)
return 1 Main method

18
animation

Trace Recursive factorial

factorial(4) returns factorial(0)


Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2 Stack

return 2 * factorial(1)
Space Required
Step 3: executes factorial(1) for factorial(1)
Step 6: return 1 Space Required
for factorial(2)
return 1 * factorial(0) Space Required
for factorial(3)
Step 4: executes factorial(0)
Step 5: return 1 Space Required
for factorial(4)
return 1 Main method

19
animation

Trace Recursive factorial

factorial(4) returns factorial(1)


Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2 Stack

return 2 * factorial(1)
Step 3: executes factorial(1)
Step 6: return 1 Space Required
for factorial(2)
return 1 * factorial(0) Space Required
for factorial(3)
Step 4: executes factorial(0)
Step 5: return 1 Space Required
for factorial(4)
return 1 Main method

20
animation

Trace Recursive factorial

factorial(4) returns factorial(2)


Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2 Stack

return 2 * factorial(1)
Step 3: executes factorial(1)
Step 6: return 1
return 1 * factorial(0) Space Required
for factorial(3)
Step 4: executes factorial(0)
Step 5: return 1 Space Required
for factorial(4)
return 1 Main method

21
animation

Trace Recursive factorial

factorial(4) returns factorial(3)


Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2 Stack

return 2 * factorial(1)
Step 3: executes factorial(1)
Step 6: return 1
return 1 * factorial(0)
Step 4: executes factorial(0)
Step 5: return 1 Space Required
for factorial(4)
return 1 Main method

22
animation

Trace Recursive factorial


returns factorial(4)

factorial(4)
Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2 Stack

return 2 * factorial(1)
Step 3: executes factorial(1)
Step 6: return 1
return 1 * factorial(0)
Step 4: executes factorial(0)
Step 5: return 1
return 1 Main method

23
factorial(4) Stack Trace
5 Space Required
for factorial(0)

4 Space Required
for factorial(1)
Space Required
for factorial(1)

3 Space Required
for factorial(2)
Space Required
for factorial(2)
Space Required
for factorial(2)

2 Space Required
for factorial(3)
Space Required
for factorial(3)
Space Required
for factorial(3)
Space Required
for factorial(3)

1 Space Required
for factorial(4)
Space Required
for factorial(4)
Space Required
for factorial(4)
Space Required
for factorial(4)
Space Required
for factorial(4)

6 Space Required
for factorial(1)
Space Required 7 Space Required
for factorial(2) for factorial(2)
Space Required Space Required 8 Space Required
for factorial(3) for factorial(3) for factorial(3)
Space Required Space Required Space Required 9 Space Required
for factorial(4) for factorial(4) for factorial(4) for factorial(4)

24
Other Examples
f(0) = 0;
f(n) = n + f(n-1);

25
Fibonacci Numbers
Fibonacci series: 0 1 1 2 3 5 8 13 21 34 55 89…
indices: 0 1 2 3 4 5 6 7 8 9 10 11

fib(0) = 0;
fib(1) = 1;
fib(index) = fib(index -1) + fib(index -2); index >=2

fib(3) = fib(2) + fib(1) = (fib(1) + fib(0)) + fib(1) =


(1 + 0) +fib(1) = 1 + fib(1) = 1 + 1 = 2

26
unsigned long Fib(unsigned long index)
{
if (index == 0)
return 0;
else if (index == 1)
return 1;
else
retrun Fib(index -1) + Fib(index-2);
}
Fibonnaci Numbers, cont.
fib(4)
17: return fib(4) 0: call fib(4)

return fib(3) + fib(2)


11: call fib(2)
10: return fib(3)

1: call fib(3) 16: return fib(2)

return fib(2) + fib(1) return fib(1) + fib(0)


7: return fib(2) 8: call fib(1) 14: return fib(0)
2: call fib(2) 13: return fib(1) 12: call fib(1)

9: return fib(1) 15: return fib(0)


return fib(1) + fib(0) return 1 return 1 return 0
4: return fib(1) 5: call fib(0)

3: call fib(1)

return 1 6: return fib(0) return 0

28
Every recursive function must be provided with
a way to end the recursion.
Otherwise it will
call itself forever and crash the program.

You might also like