Scribd Logo
Upload

Welcome to Scribd!

  • 27 views

    Esc101: Fundamentals of Computing Esc101: Fundamentals of Computing

    Uploaded by

    Mukesh Kumar Dewra
    The document discusses recursion in computing. It provides examples of recursive functions like calculating factorials and solving the Tower of Hanoi puzzle. Recursion involves a function calling itself, with successive calls using different parameters that move toward a base case. This matches the principle of mathematical induction, where a problem of size N can be solved if the problem of size N-1 can be solved and the base case of size 1 can be solved.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Esc101: Fundamentals of Computing Esc101: Fundamentals of Computing

    Uploaded by

    Mukesh Kumar Dewra
    27 views8 pages
    The document discusses recursion in computing. It provides examples of recursive functions like calculating factorials and solving the Tower of Hanoi puzzle. Recursion involves a function calling itself, with successive calls using different parameters that move toward a base case. This matches the principle of mathematical induction, where a problem of size N can be solved if the problem of size N-1 can be solved and the base case of size 1 can be solved.

    Original Title

    esc101-lec16

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses recursion in computing. It provides examples of recursive functions like calculating factorials and solving the Tower of Hanoi puzzle. Recursion involves a function calling itself, with successive calls using different parameters that move toward a base case. This matches the principle of mathematical induction, where a problem of size N can be solved if the problem of size N-1 can be solved and the base case of size 1 can be solved.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    27 views8 pages

    Esc101: Fundamentals of Computing Esc101: Fundamentals of Computing

    Uploaded by

    Mukesh Kumar Dewra
    The document discusses recursion in computing. It provides examples of recursive functions like calculating factorials and solving the Tower of Hanoi puzzle. Recursion involves a function calling itself, with successive calls using different parameters that move toward a base case. This matches the principle of mathematical induction, where a problem of size N can be solved if the problem of size N-1 can be solved and the base case of size 1 can be solved.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 8

    ESc101: Fundamentals of Computing

    2011-12-Monsoon Semester Lecture #16, September 1, 2011

    Please switch off your mobile phones.

    Announcements
    Wednesday lab scheduled on 31st August will instead be held y p on Saturday, 3rd September from 2:00 PM to 5:00 PM. Quiz on lab days from 5th to 9th September in Lab at 2:00 PM.
    Please ensure that you have moodle access and Computer Center access. If you have forgotten either password, please make sure that you get the problem sorted out before the quiz. No makeup for the quiz.

    Mid-semester exam at 7:30 AM on 14th September, 2011.

    Lec-16

    Dheeraj Sanghi, CSE Dept., IIT Kanpur ESc101, 2011-12-Monsoon

    Best Programmer for Lab 03


    Section E1 E3 E5 E7 E9 E11 E13 E15 Name Prateek Sahu Rahul Sankhwar Ayush Pandey Shubham Singh Rithwik J Cherian Sarthak Chandra Anurag Sahay None Section E2 E4 E6 E8 E10 E12 E14 Name Vibhu Mohan Bajpai Piyush Kumar None Nikunj Agrawal Swapnil Samir Poal Shreshth Gandhi Jitendra Kumar

    Lec-16

    Dheeraj Sanghi, CSE Dept., IIT Kanpur ESc101, 2011-12-Monsoon

    Recap
    Single dimensional arrays as p g y parameters in functions Recursion an introduction

    Lec-16

    Dheeraj Sanghi, CSE Dept., IIT Kanpur ESc101, 2011-12-Monsoon

    Recap: Recursion - Example

    int {

    fact (int n) if ((n == 1) || (n == 0)) return 1; return n * fact (n -1); ( )

    Lec-16

    Dheeraj Sanghi, CSE Dept., IIT Kanpur ESc101, 2011-12-Monsoon

    Recursion
    Recursion refers to one function calling itself. itself It can also refer to a cyclic function call.
    If Function f1() calls Function f2(), Function f2() calls Function f3(), and Function f3() calls Function f1()

    Successive recursive calls should be with different parameters, otherwise we can get into an infinite recursion. Th must be a base case, a set of parameters for which There tb b t f t f hi h the answer is returned without further calls. The parameters in successive should be moving towards the base case.
    Lec-16 Dheeraj Sanghi, CSE Dept., IIT Kanpur ESc101, 2011-12-Monsoon 5

    Example: Factorial
    #include <stdio.h> int factorial (int n) { if ((n == 1) || ( == 0)) (( (n // base case: n is 0 or 1 b i return 1; return n * factorial (n-1); // next call is different and } // moves towards base case int main () { int n; scanf (%d, &n); printf (Factorial = %d\n, factorial (n)); }
    Lec-16 Dheeraj Sanghi, CSE Dept., IIT Kanpur ESc101, 2011-12-Monsoon 6

    Recursion: Local variables


    Each call to the function is treated as a new instance of that function. Every call to a function results in all local variables of that function being given new memory areas.

    Lec-16

    Dheeraj Sanghi, CSE Dept., IIT Kanpur ESc101, 2011-12-Monsoon

    Recursion: Example: Tower of Hanoi


    Problem:
    There are N disks on a needle. All N disks are of different sizes. And smaller disk cannot be below a larger disk. There are two empty needles available. All N disks have to be moved to one of the empty needle. One O can move only one disk at a time. l di k i At no time can there be a smaller disk below a larger disk.

    Lec-16

    Dheeraj Sanghi, CSE Dept., IIT Kanpur ESc101, 2011-12-Monsoon

    Tower of Hanoi - Algorithm


    Let us call three needles, A, B, and C. needles A B C Let us assume that all disks are on needle A. Let us assume that all disks are to be move to needle B To move N disks from A to B using C we do the following:
    Move (N-1) disks from A to C using B Move Nth disk from A to B Move (N-1) disks from C to B using A

    Lec-16

    Dheeraj Sanghi, CSE Dept., IIT Kanpur ESc101, 2011-12-Monsoon

    Tower of Hanoi - Example


    The base case is when one has to only move one disk. disk The recursive case keeps getting smaller and moves towards the base case. The assumption is that N disks can move ONLY IF there is a way to move N-1 disks. If we can move N-1 disks then two moves of N-1 disks and a single move of a single disk will solve the problem. i l f i l di k ill l th bl Based on principle of induction.

    Lec-16

    Dheeraj Sanghi, CSE Dept., IIT Kanpur ESc101, 2011-12-Monsoon

    10

    Recursion: Principle of Induction


    Principle of Induction:
    If a statement is true for N = 1 And if the assumption that the statement is true for N = x implies that the statement is true for N = x+1 Then the statement is true for all natural numbers.

    This is exactly what we have used in recusrion.


    Sh Shown th t we can solve the problem of size = 1 (base case) that l th bl f i (b ) Shown that if we can solve the problem of size N-1 then the problem of size N can be solved (recursive case) Hence problem can be solved for all values of N
    Lec-16 Dheeraj Sanghi, CSE Dept., IIT Kanpur ESc101, 2011-12-Monsoon 11

    Recursion: Power (Example)


    Recursive definition of power can be expressed as following. power (x, n) = ?
    1, if n == 0 x * square (power(x, n/2)), if n is odd square (power(x, n/2)), if n is even

    Lec-16

    Dheeraj Sanghi, CSE Dept., IIT Kanpur ESc101, 2011-12-Monsoon

    12

    Power function
    #include <stdio.h> int power (int x, int n) { int t; if (n == 0) return 1; t = power (x, n/2); if (n%2 != 0) return x * t * t; return t * t; } int main () { i int n, x; scanf (%d %d, &n, &x); printf (power is %d\n, power(x, n)); }
    Lec-16 Dheeraj Sanghi, CSE Dept., IIT Kanpur ESc101, 2011-12-Monsoon 13

    Any Questions?

    Lec-16

    Dheeraj Sanghi, CSE Dept., IIT Kanpur ESc101, 2011-12-Monsoon

    14

    You might also like