Difference between revisions of "BASH/C3/Recursive-function/English"

From Script | Spoken-Tutorial
Jump to: navigation, search
(Created page with ''''Title of script: Advance topics in function ''' '''Author:''' Lavitha Pereira '''Keywords: Video tutorial, recursive function''' {| style="border-spacing:0;" | style="bord…')
 
 
Line 20: Line 20:
 
* '''What is a Recursive''' function?
 
* '''What is a Recursive''' function?
 
* With the help of some examples  
 
* With the help of some examples  
 
 
  
 
|-
 
|-
Line 31: Line 29:
  
 
If not, for relevant tutorials please visit our website which is as shown,'''(http://www.spoken-tutorial.org)'''
 
If not, for relevant tutorials please visit our website which is as shown,'''(http://www.spoken-tutorial.org)'''
 
 
  
  
Line 50: Line 46:
  
 
'''Recursion'''
 
'''Recursion'''
 
  
  
Line 57: Line 52:
 
* A '''recursive function''' is one which calls itself
 
* A '''recursive function''' is one which calls itself
 
* '''Recursion''' is a useful technique for simplifying complex algorithms
 
* '''Recursion''' is a useful technique for simplifying complex algorithms
 
  
  
Line 79: Line 73:
 
'''}'''
 
'''}'''
 
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| '''factorial '''is the function name.  
 
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| '''factorial '''is the function name.  
 
and it is an empty function.
 
 
 
 
  
 
|-
 
|-
 
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| '''factorial() { '''
 
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| '''factorial() { '''
  
'''echo "We are inside a factorial function" '''
+
'''echo "Inside factorial function" '''
  
 
'''}'''
 
'''}'''
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| Let's write a line of code that will print a message “We are inside a factorial function”
+
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| Inside this, we print a message “Inside factorial function”
 
+
 
+
  
  
Line 101: Line 88:
 
'''read -p "Enter the number:" n '''
 
'''read -p "Enter the number:" n '''
 
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| This statement reads user's input and stores the value in variable ''''n''''
 
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| This statement reads user's input and stores the value in variable ''''n''''
 
 
  
  
Line 109: Line 94:
  
 
'''echo "factorial value of $n is 1"'''
 
'''echo "factorial value of $n is 1"'''
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| Here I have an '''if-else condition.'''
+
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| Here we have '''if-else condition.'''
  
 
'''If '''condition checks whether the value of''' 'n'''' is '''equal to zero.'''
 
'''If '''condition checks whether the value of''' 'n'''' is '''equal to zero.'''
  
If '''true, '''it will display the message '''"factorial value of 0 is 1".'''
+
If '''true, '''it will display the message '''"factorial value of n is 1".'''
  
 
|-
 
|-
Line 127: Line 112:
 
It calls the '''factorial function.'''
 
It calls the '''factorial function.'''
  
'''And fi '''is the end of the '''if-else''' statement.
+
And '''fi '''is the end of the '''if-else''' statement.
  
 
|-
 
|-
Line 151: Line 136:
 
|-
 
|-
 
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| Type:'''0'''
 
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| Type:'''0'''
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| I will enter '''0''' and press''' Enter.'''
+
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| We see '''"Enter the number"'''.
 +
 
 +
I will enter '''0'''.
  
 
|-
 
|-
Line 157: Line 144:
  
 
'''Output'''
 
'''Output'''
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| We see the output as:
+
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| The output is displayed as:
  
 
'''factorial value of 0 is 1'''
 
'''factorial value of 0 is 1'''
Line 173: Line 160:
 
Press '''Enter.'''
 
Press '''Enter.'''
  
This time, I will enter''' 5 '''and press''' Enter.'''
+
This time, I will enter''' 5 '''.
  
 
|-
 
|-
Line 179: Line 166:
  
 
'''Output'''
 
'''Output'''
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| The output is:
+
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| Now the output is displayed as:
  
'''We are inside a factorial function.'''
+
'''Inside factorial function.'''
  
 
|-
 
|-
 
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"|  
 
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"|  
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| Now let us add some more logic to the '''factorial function.'''
+
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| Let us add some more logic to the '''factorial function.'''
  
 
We will calculate the '''factorial''' of a number.
 
We will calculate the '''factorial''' of a number.
Line 213: Line 200:
  
 
'''fi'''
 
'''fi'''
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| Now let us replace, the echo statement inside the factorial function with the code block.
+
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| Now let us replace, the '''echo statement''' inside the '''factorial function''' with the code block.
  
 
Click on '''Save'''
 
Click on '''Save'''
 
 
  
  
Line 230: Line 215:
 
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| '''If condition''' checks whether the variable value is equal to 1'''.'''
 
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| '''If condition''' checks whether the variable value is equal to 1'''.'''
  
If true, it will prints 1.
+
If '''true''', it will print 1.
  
 
|-
 
|-
Line 254: Line 239:
  
 
'''echo $f '''
 
'''echo $f '''
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| Value of variable f and temp is multiplied and stored in f.
+
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| Value of variable '''f''' and '''temp''' is multiplied and stored in '''f'''.
  
Then we print the vaue of '''f.'''
+
Then we print the value of '''f.'''
  
 
|-
 
|-
Line 266: Line 251:
 
|-
 
|-
 
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"|  
 
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"|  
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| Save the file and come to the '''slides.'''
+
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| Now come back to our '''slides.'''
  
 
Let us understand the flow of the program.
 
Let us understand the flow of the program.
Line 274: Line 259:
  
 
'''<nowiki><<</nowiki>Flowchart>>'''
 
'''<nowiki><<</nowiki>Flowchart>>'''
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| # The value of '''n''' is taken from the user ie '''n'''
+
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| # The value of '''n''' is taken from the user i.e. '''n'''
# If the value entered is equal to zero then it prints a message
+
# If the value entered is equal to zero, then it prints a message
 
# Else it goes to the function '''factorial'''
 
# Else it goes to the function '''factorial'''
# Here, if the value is equal to one then it prints value as one
+
# Here, if the value is equal to one, then it prints value as one
# If not, it makes a recursive call until the value is equal to one
+
# If not, it makes a '''recursive call''' until the value is equal to one
 
# Then, all the values are multiplied and displayed
 
# Then, all the values are multiplied and displayed
 
  
  
Line 289: Line 273:
  
 
Press '''Enter'''
 
Press '''Enter'''
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| Now come back to the terminal.
+
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| Now come back to the '''terminal'''.
  
 
Press the '''uparrow''' key.
 
Press the '''uparrow''' key.
Line 305: Line 289:
 
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| We get the '''factorial '''of number 5.
 
| style="border-top:none;border-bottom:1pt solid #000001;border-left:1pt solid #000001;border-right:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| We get the '''factorial '''of number 5.
  
'''ie 120.'''
+
'''i.e. 120.'''
  
 
|-
 
|-
Line 330: Line 314:
 
* '''Recursive''' function
 
* '''Recursive''' function
 
* With the help of some examples  
 
* With the help of some examples  
 
 
  
 
|-
 
|-
Line 339: Line 321:
 
| style="border:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| As an assignment.
 
| style="border:1pt solid #000001;padding-top:0cm;padding-bottom:0cm;padding-left:0.191cm;padding-right:0.191cm;"| As an assignment.
  
Write a program,
+
Write a program where the '''recursive function''' calculates the sum of''' N '''numbers
 
+
* where the recursive function calculates the sum of''' N '''numbers
+
 
+
  
  

Latest revision as of 20:37, 15 June 2014

Title of script: Advance topics in function

Author: Lavitha Pereira

Keywords: Video tutorial, recursive function


Visual Cue
Narration
Display Slide 1 Dear friends, welcome to the spoken tutorial on Recursive function.
Display Slide 2 In this tutorial, we will learn
  • What is a Recursive function?
  • With the help of some examples
Display Slide 3Prerequisites


To follow this tutorial, you should have knowledge of Shell Scripting in BASH.

If not, for relevant tutorials please visit our website which is as shown,(http://www.spoken-tutorial.org)


Display Slide 4

System requirements

For this tutorial I am using
  • Ubuntu Linux 12.04 Operating System and
  • GNU BASH version 4.2

Please note, GNU Bash version 4 or above is recommended to practice this tutorial.

Display slide 8

Recursion


Let us see what a recursive function is.
  • A recursive function is one which calls itself
  • Recursion is a useful technique for simplifying complex algorithms


Let me open a file named factorial.sh
Highlight

#!/usr/bin/env bash

I have typed some code in this file.

This is the shebang line.

factorial()

{

}

factorial is the function name.
factorial() {

echo "Inside factorial function"

}

Inside this, we print a message “Inside factorial function”


#main script

read -p "Enter the number:" n

This statement reads user's input and stores the value in variable 'n'


if [ $n -eq 0 ]; then

echo "factorial value of $n is 1"

Here we have if-else condition.

If condition checks whether the value of 'n' is equal to zero.

If true, it will display the message "factorial value of n is 1".

else

#calling factorial function

factorial $n

fi

Here is the else part of the if statement.

It calls the factorial function.

And fi is the end of the if-else statement.

Switch to terminal Let us run the file factorial.sh.

Open the terminal using CTRL+ALT+T keys simultaneously on your keyboard.

Type

chmod +x factorial.sh>>Press Enter

dot slash factorial.sh

Type:chmod space plus x space factorial dot sh

Press Enter.

Type dot slash factorial.sh

Press Enter.

Type:0 We see "Enter the number".

I will enter 0.

Highlight

Output

The output is displayed as:

factorial value of 0 is 1

dot slash factorial.sh

Type:

5

Now press the uparrow key.

Recall the previous command.

Press Enter.

This time, I will enter 5 .

Highlight

Output

Now the output is displayed as:

Inside factorial function.

Let us add some more logic to the factorial function.

We will calculate the factorial of a number.

Come back to our code.

Type:

temp=$1

if [ $temp -eq 1 ]; then

echo "1"

else

f=$((temp-1))

#Recursive call

f=$(factorial $f)

f=$((f*temp))

echo $f

fi

Now let us replace, the echo statement inside the factorial function with the code block.

Click on Save


temp=$1 temp is a variable and stores the value entered by user.
if [ $temp -eq 1 ]; then

echo “1”

If condition checks whether the variable value is equal to 1.

If true, it will print 1.

else

f=$((temp-1))

This is the else part of the if statement.

This reduces one from the temp variable value.

And stores the result in a variable 'f'.

#Recursive call

f=$(factorial $f)

Variable f stores the output of factorial function.

This is a recursive call.

f=$((f*temp))

echo $f

Value of variable f and temp is multiplied and stored in f.

Then we print the value of f.

fi

}

End of if-else statement and function.
Now come back to our slides.

Let us understand the flow of the program.

Workflow of Program

<<Flowchart>>

# The value of n is taken from the user i.e. n
  1. If the value entered is equal to zero, then it prints a message
  2. Else it goes to the function factorial
  3. Here, if the value is equal to one, then it prints value as one
  4. If not, it makes a recursive call until the value is equal to one
  5. Then, all the values are multiplied and displayed


[Highlight]

./factorial.sh

Press Enter

Now come back to the terminal.

Press the uparrow key.

Recall the previous command.

./factorial.sh

Press Enter.

Now I will enter 5 as the input value.

Output We get the factorial of number 5.

i.e. 120.

Terminal

[Output]


We can see the flow of the program on terminal.

Analyse and trace the flow of program.

Come back to our slides.

Display Slide 10

Summary

Let us summarise.

In this tutorial we have learnt,

  • Recursive function
  • With the help of some examples
Display Slide 10

Assignment

As an assignment.

Write a program where the recursive function calculates the sum of N numbers


Display Slide 11

http://spoken-tutorial.org /What\_is\_a\_Spoken\_Tutorial

About the Spoken Tutorial Project

Watch the video available at the link shown below.


It summarises the Spoken Tutorial project.


If you do not have good bandwidth, you can download and watch it.

Display Slide 12

Spoken Tutorial Workshops

The Spoken Tutorial Project Team
  • Conducts workshops using spoken tutorials
  • Gives certificates to those who pass an online test

For more details, please write to

contact@spoken-tutorial.org

Display Slide 13

Acknowledgement

Spoken Tutorial Project is a part of the Talk to a Teacher project.


It is supported by the National Mission on Education through ICT, MHRD, Government of India.


More information on this Mission is available at:

http://spoken-tutorial.org\NMEICT-Intro

Display Slide 14 The script has been contributed by FOSSEE and Spoken-Tutorial teams.


This is Ashwini from IIT Bombay.

Thank you for joining.

Contributors and Content Editors

Ashwini, Nancyvarkey