Recursion in function use

• Process of solving a problem using solutions to “smaller” versions of the same problem!
• You have already encountered recursion in mathematics
• Factorial function is defined in terms of factorial itself!

​

• Proof by induction is basically a recursive proof
• Claim: 1 + 2 + 3 + … + n = n(n+1)/2
• Proof: Base case: for n = 1 true by inspection
• Inductive case: (1 + … + n) = (1 + … + n-1) + n = (n-1)n/2 + n = n(n+1)/2 ☺
• Notice that we need a base case and recursive case
• In case of factorial, fac(0) was the base case.
• This is true when writing recursive functions in C language as well

1

We used the proof for the case n-1 to prove the case n

Factorial

2

int fact(int a){

if(a == 0) return 1;

return a * fact(a - 1);

}

int main(){

printf("%d", fact(1+1));

}

2

2

1

1

0

0

1

1

2

2

2

1

1

Recap – 6 basic rules of C functions

• RULE 1: When we give a variable as input, the value stored inside that variable gets passed as an argument
• RULE 2: When we give an expression as input, the value generated by that expression gets passed as argument
• RULE 3: In case of a mismatch b/w type of arg promised and type of arg passed, typecasting will be attempted
• RULE 4: All values passed to a function get stored in a fresh variable inside that function (changes made to this variable won’t change the original var regardless of whether it is a normal var or pointer)
• RULE 5: Value returned by a function can be used freely in any way values of that data-type could have been used
• RULE 6: All clones share the memory address space

3

Output

4

#include<stdio.h>

int recursive(int i) {

static int count = 0;

count = count + i;

return count;

}

​

int main() {

int i, j;

for (i = 0; i <= 5; i++)

j = recursive(i);

printf("%d\n", j);

return 0;

}