Scribd
Upload
6 views12 pages

Understanding Recursion in Programming

The document explains recursion, focusing on the concept of recursive functions that call themselves, exemplified by calculating the factorial of an integer. It outlines the two main components of a recursive function: the base case and the recursive step, and provides both recursive and non-recursive implementations for factorial and product calculations. Additionally, it includes exercises for further practice on recursive functions.

Uploaded by

Joshua Tomas
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
6 views12 pages

Understanding Recursion in Programming

The document explains recursion, focusing on the concept of recursive functions that call themselves, exemplified by calculating the factorial of an integer. It outlines the two main components of a recursive function: the base case and the recursive step, and provides both recursive and non-recursive implementations for factorial and product calculations. Additionally, it includes exercises for further practice on recursive functions.

Uploaded by

Joshua Tomas
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

CmpSc 133
Recursion
A recursive function is one that calls on itself

Consider finding the factorial of an integer N


N! = 1*2*3* . . . *N

Ex: 6! = 1*2*3*4*5*6
= 6*5*4*3*2*1
Two Parts of a recursive function
1. Anchor case or Base Case –specifies the value of the function for
one or more values
Two Parts of a recursive function
1. Anchor case or Base Case –specifies the value of the function for
one or more values
2. Recursive or Inductive Step – the value of the function is defined in
terms of previously defined function values
Non-recursive Version
Factorial = 1
For i=1 to N do
factorial = factorial * i
Non-recursive Version
Factorial = 1
For i=1 to N do
factorial = factorial * I
Ex: 5! = ??
factorial =1
for i = 1 to 5
i= 1 factorial =1
2 2
3 6
4 24
5 120
Recursive Version
Function FACTORIAL(N)

if N = 0 then FACTORIAL(N) = 1 /* base case*/


else FACTORIAL=N*FACTORIAL(N-1) /*recursive step*/
Ex: 5!
FACTORIAL(5)= 5*FACTORIAL(4)
Recursive Version
Function FACTORIAL(N)
if N = 0 then FACTORIAL(N) = 1 /* base case*/
else FACTORIAL=N*FACTORIAL(N-1) /*recursive step*/
Ex: 5!
FACTORIAL(5)= 5*FACTORIAL(4) 5*24=120
4*FACTORIAL(3) 4*6=24
3*FACTORIAL(2) 3*2=6
2*FACTORIAL(1) 2*1=2
1*FACTORIAL(0) 1*1=1
1 →
Another Example
Calculate xn = x. x .x….x (multiply x n times)

Non recursive function:


PRODUCT (x; n) {multiply x n times}
product = 1
for I = 1 to n
product = product . x
Recursive version

PRODUCT (x;n)
if n = 1 then product(x,n) = x {base case}
else
product = x * product(x,n-1) {recursive step}
Exercises
1. Determine what is computed by the recursive function
function F(n:integer):integer
begin
if n<2 then
F:=0
else
F:= 1 + F(n div 2)
end
Exercises
2. Write a recursive function to generate the Fibonacci sequence
1,1,2,3,5,8,13,21,34,55, . . .
3. Write a recursive procedure to dislay the digits of a nonzero integer
in reverse order (e.g. 1234 → 4321)
4. Write a non recursive version for #1.

You might also like