Recursive Functions in C Programming
Recursion in C allows functions to operate on themselves, leading to concise and understandable forms. This post covers examples of recursive functions like factorial and Fibonacci in C programming, exploring the concept and benefits of recursion over iteration.
Uploaded on Feb 18, 2025 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
COM101B LECTURE 10: RECURSIVE FUNCTIONS ASST. PROF. DR. HACER YALIM KELE REFERENCE: PROGRAMMING IN ANSI C , KUMAR & AGRAWAL, WEST PUBLISHING CO., 1992
RECURSION Recursion is the process that a construct operates on itself. In C, functions can be defined recursively; a function may call itself directly, a function calls another function, then that function calls this function back, i.e. indirect recursion. REFERENCE: PROGRAMMING IN ANSI C , KUMAR & AGRAWAL, WEST PUBLISHING CO., 1992
Example: Factorial function int factorial(int N) { if (N==0) return 1; // base case: termination condition else return N * factorial(N-1); // recurse } REFERENCE: PROGRAMMING IN ANSI C , KUMAR & AGRAWAL, WEST PUBLISHING CO., 1992
Recursive evaluation of factorial(3) REFERENCE: PROGRAMMING IN ANSI C , KUMAR & AGRAWAL, WEST PUBLISHING CO., 1992
Example: Fibonacci numbers Sequence of numbers: {1,1,2,3,5,8,13,...} fib(0) = fib(1) = 1 fib(n) = fib(n-1) + fib(n-2), n>1 int fib(int n) { return n==0 || n==1 ? 1 : fib(n-1) + fib(n-2); } REFERENCE: PROGRAMMING IN ANSI C , KUMAR & AGRAWAL, WEST PUBLISHING CO., 1992
Recursive evaluation of fib(3) REFERENCE: PROGRAMMING IN ANSI C , KUMAR & AGRAWAL, WEST PUBLISHING CO., 1992
ITERATIVE VERSION OF FIBONACCI REFERENCE: PROGRAMMING IN ANSI C , KUMAR & AGRAWAL, WEST PUBLISHING CO., 1992
PROPERTIES OF RECURIVE FUNCTIONS The recursive versions of most of the function (when appropriate) have more concise and understandable form than their iterative versions. However, compared to their iterative versions, recursive versions are more inefficient Function call stack is enlarging very fast passing arguments to each recursion branch makes it inefficient REFERENCE: PROGRAMMING IN ANSI C , KUMAR & AGRAWAL, WEST PUBLISHING CO., 1992
IMPLEMENTATION CHALLENGE - RECURSION Tower of Hanoi Puzzle: The objective: to move the entire stack to the other rod, obeying the following rules: 1-Only one disk can be moved at a time 2-You can only move the upper disk at a time, and can be placed at the top of the other stack 3-No disk can be placed on top of a smaller disk. REFERENCE: PROGRAMMING IN ANSI C , KUMAR & AGRAWAL, WEST PUBLISHING CO., 1992
READING ASSIGNMENT Read and implement Section 5.9.2 (Tower of Hanoi Puzzle) REFERENCE: PROGRAMMING IN ANSI C , KUMAR & AGRAWAL, WEST PUBLISHING CO., 1992
