ICS 1201 4/17/2025

Introduction
• Recursion: 0! = 1 (By Definition!)
– Process of solving a problem by n! = n x (n – 1) ! If n > 0
reducing it to smaller versions of itself 3! = 3 x 2!
2! = 2 x 1!
• Recursive algorithm:
Recursion – Algorithm that finds the solution to a
given problem by reducing the problem
1!

0! =
= 1 x 0!

1 (Base Case!)
to smaller versions of itself
– Has one or more base cases 1! = 1 x 0! = 1x1=1
2! = 2 x 1! = 2x1=2
– Implemented using recursive methods
3! = 3 x 2! = 3x2=6

Definitions Example 1: Factorial of a Number

0! = 1 (By Definition!)
• Recursive method: 0! = 1 (By Definition!) • Factorial of n, or n! is the product: n! = n x (n – 1) ! If n > 0
– Method that calls itself n! = n x (n – 1) ! If n > 0 3! = 3 x 2!
3! = 3 x 2! n · (n – 1) · (n – 2) · … · 1 2! = 2 x 1!
• Base case: 2! = 2 x 1! • With 1! equal to 1 and 0! defined to be 1. 1! = 1 x 0!
– Case in recursive definition in which the 1! = 1 x 0!
solution is obtained directly • Can be solved recursively or iteratively 0! = 1 (Base Case!)
– Stops the recursion 0! = 1 (Base Case!)
• Recursive solution uses following
1! = 1 x 0! = 1x1=1
• General case: 1! = 1 x 0! = 1x1=1 relationship: n! = n · (n – 1)! 2! = 2 x 1! = 2x1=2
– Case in recursive definition in which a 2! = 2 x 1! = 2x1=2 3! = 3 x 2! = 3x2=6
smaller version of itself is called 3! = 3 x 2! = 3x2=6
– Must eventually be reduced to a base case

4
ICS 1201 4/17/2025

Factorial of a Number Using Iteration Factorial of a Number Using Recursion

The method is
First call of the method
n = int (input ("Enter a number: ")) first call
n = 4 (factorial (4))
factorial = 1 Return value: 24  4x6
if n >= 1: Second call of the method
n = 3 (factorial (3))
for i in range (1, n+1): Return value: 6  3x2
factorial=factorial *i Third call of the method
n = 2 (factorial (2))
print("Factorial number is: ", factorial) Return value: 2  2x1
print(factorial(4))
Fourth call of the method
n = 1 (factorial (1))
Return value: 1

Factorial of a Number Using Recursion Example 2: Power of a Number

• Can be solved using either recursion or iteration
ICS 1201 4/17/2025

Power of a Number (xy ) Using Iteration Power of a Number Using Recursion

# creating a function that returns the power of a Number def power(base,exp):
# It accepts Number, and exponent values as parameters if(exp==1):
def findPower(number, exponent): return(base)
# intializing a variable with 1 (it stores the resultant power) if(exp!=1):
resultPower =1 return(base*power(base,exp-1))
# traversing in the range from 1 to given exponent+1 base=int(input("Enter base: "))
for i in range(1, exponent+1): exp=int(input("Enter exponential value: "))
# Multiplying the result with the given number print("Result:",power(base,exp))
resultPower=resultPower*number
# returning the resultant power
return resultPower

Example 3: Fibonacci Series Fibonacci

Series
Using
Iteration
ICS 1201 4/17/2025

Fibonacci Series Using Recursion Fibonacci Series Using Recursion

13
Two base cases

Two recursive calls

Set of recursive calls for fibonacci( 3 ).

14

Tracing a Recursive Method Additional Definitions

• Recursive method: • Directly recursive: a method that calls itself
– Logically, you can think of a recursive • Indirectly recursive:
method having unlimited copies of
itself • A method that calls another method and eventually results in the original method call.
– Every recursive call has its own set of First call of the method • Method A calls method B, which in turn calls method A.
local variables. n = 4 (factorial (4)) • Infinite recursion:
• After completing a recursive call: Return value: 24
– Case where every recursive call results in another recursive call.
– Control goes back to the calling Second call of the method
– It is caused by either omitting the base case or writing recursion step that does not converge on
environment n = 3 (factorial (3))
base case.
Return value: 6
– Each recursive call must execute – Memory may get exhausted.
completely before control goes back to Third call of the method
n = 2 (factorial (2)) – In designing or programming recursive algorithms, this should not be allowed to happen
previous call
Return value: 2
– Execution in previous call begins from
point immediately following recursive Fourth call of the method
call n = 1 (factorial (1))
Return value: 1
ICS 1201 4/17/2025

Designing Recursive Methods Common Programming Errors in Recursion

• Understand problem • Infinite direct recursion:
0! = 1 (By Definition!)
requirements n! = n x (n – 1) ! If n > 0 – Either omitting the base case or writing the recursion step incorrectly so that it does not
• Base case: 3! = 3 x 2! converge on the base case can cause a logic error known as infinite recursion, where recursive
2! = 2 x 1! calls are continuously made until memory has been exhausted.
– Identify base cases 1! = 1 x 0! – This error is analogous to the problem of an infinite loop in an iterative (non-recursive) solution.
– Provide direct solution to each base
case 0! = 1 (Base Case!) • Infinite indirect recursion: Accidentally having a non-recursive method call itself
• General case: either directly or indirectly through another method can cause infinite recursion.
1! = 1 x 0! = 1x1=1
– Identify general case(s) 2! = 2 x 1! = 2x1=2
– Provide solutions to general cases in 3! = 3 x 2! = 3x2=6
terms of smaller versions of general
cases

18

Comparison of Recursion and Iteration Software Engineering Observations

• Any problem that can be solved recursively can be solved iteratively. • Any problem that can be solved recursively can also be solved iteratively (non-
• Both iteration and recursion use a control statement: recursively).
– Iteration uses a repetition statement • A recursive approach is normally preferred over an iterative approach when the
– Recursion uses a selection statement recursive approach more naturally mirrors the problem and results in a program
• Iteration and recursion both involve a termination test: that is easier to understand and debug.
– Iteration terminates when the loop-continuation condition fails • A recursive approach can often be implemented with fewer lines of code.
– Recursion terminates when a base case is reached • Another reason to choose a recursive approach is that an iterative one might not be
• Recursion can be expensive in terms of processor time and memory space, but apparent.
usually provides a more intuitive solution.

19 20