recursion

Aladdin

Oct 15, 2019 07:20

@JohnRennie factorial(5) = 5 * factorial(4)
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1 * factorial(0)
factorial(0) = 1
factorial(1) = 1 * 1 = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24
factorial(5) = 5 * 24 = 120
Each indentation level ^ there corresponds to a level in a recursive call stack. factorial(5) can only return if its call to factorial(4) returns, and so on. So you go down deeper and deeper until factorial(0) can return literal 1 to its caller factorial(1), then factorial(1) ca…

We will discuss this later

For now, tell me about how to check factor using recursion

John Rennie

That's why the code has:

if n == 0:
    return 1

That means factorial(0) immediately returns 1

Actually you could improve that since factorial(1) is 1 as well. I would write:

Aladdin

Ok

John Rennie

if n == 0 or n == 1:
    return 1

Those are the two special cases of the factorial function.

Aladdin

@JohnRennie How to find gcd

is there an inbuilt function

John Rennie

@Aladdin I'll have to read up on the algorithm for finding the GCD since I don't know how it works. That will take me a few minutes. You need to do the same since if you don't understand the method you won't understand the code.

Aladdin

Oct 15, 2019 07:32

ohkay

John Rennie

@Aladdin OK, I've read up on the algorithm. Do you want to go through it?

Aladdin

yes

@JohnRennie Yes

John Rennie

Suppose we have two numbers A and B with a greatest common divisor G.

Then we can write A = aG and B = bG where a and b are integers. OK so far?

Aladdin

ok

John Rennie

Oct 15, 2019 07:48

We'll assume A > B. Then A - B = aG - bG = (a-b)G. So G is also a divisor of A-B. If we call C = A - B then C = cG for some new smaller integer C.

Aladdin

yes

John Rennie

So what we do is set C = A - B and now we have a new pair of numbers C = cG and B = bG.

Aladdin

yes

John Rennie

And we can now repeat the process. e.g. suppose B is now the larger number then if we set D = B - C the difference must also be a multiple of G i.e. D = dG.

Aladdin

yep

John Rennie

Oct 15, 2019 07:52

So what we are doing is repeatedly subtracting some (unknown) multiple of G from our numbers.

Aladdin

ok

John Rennie

i.e. after the subtraction we are left with some multiple of G, xG, where we don't know the value of x.

But x has to be an integer so the smallest possible value of x is x = 1

Aladdin

@JohnRennie hi i need to go now

I will return after an hour

John Rennie

OK, I'll still be around.

Aladdin

Can we discuss then?

John Rennie

Oct 15, 2019 07:55

@Aladdin yes

Aladdin

Oct 15, 2019 09:05

@JohnRennie hI

John Rennie

@Aladdin hi

Aladdin

ok so your logic is

if a nad b have a gcd

then a-b,a will also have same gcd

John Rennie

Yes. Let's take an example to illustrate this.

Suppose A = 8 and B = 6, so the GCD is 2. A = 4 x 2 and B = 3 x 2.

Then A - B = (4 x 2) - (3 x 2) = 1 x 2 = 2

Aladdin

yes

@JohnRennie So what will be the progrme be

using recursion

John Rennie

Now replace the large number, A, by the difference. Our two numbers are now B = 6 and the number we got from the difference C = 2.

Aladdin

Oct 15, 2019 09:11

ye

yes

John Rennie

And this is where the recursion comes in because now we repeat the process with our new numbers B and C.

Aladdin

so when should the recursion stop

John Rennie

The difference is B - C = 4. Call this D, so now we have C = 2 and D = 4.

Aladdin

yes

John Rennie

And we do this again. the difference is E = D - C = 2 so now we have the two numbers E = 2 and C = 2.

Aladdin

Oct 15, 2019 09:14

yes

John Rennie

But now our two numbers are the same, and if they are the same their common divisor is just the same as the two numbers.

So this is where we stop.

Aladdin

wait

if i take

a=57

sorry a=56

b=76

then how will thi work

John Rennie

56 = 7 x 2 x 2 x 2

76 = 19 x 2 x 2

So the gcd is going to be 4. Yes?

Aladdin

yes

John Rennie

Ok, shall we go through the calculation manually?

Aladdin

Oct 15, 2019 09:19

let's go for once

John Rennie

First step: 56 and 76 aren't the same, so we replace the larger number by the difference. That gives us the two numbers 56 and 20.

Aladdin

yes

John Rennie

Second step: 56 and 20 aren't the same, so we replace the larger number by the difference. That gives us the two numbers 36 and 20.

Aladdin

yes

John Rennie

Third step: 36 and 20 aren't the same, so we replace the larger number by the difference. That gives us the two numbers 20 and 16.

Fourth step: 20 and 16 aren't the same, so we replace the larger number by the difference. That gives us the two numbers 16 and 4.

Aladdin

Oct 15, 2019 09:22

yes

John Rennie

Fifth step: 16 and 4 aren't the same, so we replace the larger number by the difference. That gives us the two numbers 12 and 4.

Sixth step: 12 and 4 aren't the same, so we replace the larger number by the difference. That gives us the two numbers 8 and 4.

Aladdin

@JohnRennie Ok a doubt

John Rennie

Yes?

Aladdin

if they have gcd then eventually the diference has to become the gcd

s that's what is happening

John Rennie

Yes, that's right.

Aladdin

Oct 15, 2019 09:23

and then the number is mutiple o gcd

so eventually it has to become equal to gcd upon substracting

John Rennie

When the difference is the gcd that means the smaller number is the gcd and the larger is twice the gcd.

Aladdin

yes

John Rennie

So we could use this as the condition for stopping.

Aladdin

ah okay

got it

@JohnRennie Last dooub on this

John Rennie

Yes?

Aladdin

Oct 15, 2019 09:25

let's take 7 and 11

so a=7

b=11

so b=-a=4

and we do gcd(7,4)

again 7-4=3

so we aagain do (3,4)

again 4-3=

1

s gcd(1,3)

@JohnRennie Yeah it's working

John Rennie

:-)

Aladdin

@JohnRennie Python 3.8 is out

do i need to work on that rom now

John Rennie

No, the difference between 3.8 and 3.7 isn't very big. You can upgrade if you want, but it won't make any difference to the sorts of program you're working on at the moment.

Aladdin

ohkay

ok i am updating

@JohnRennie when you are free

practicum.tech/recurser

explain the fibonacci program from there

how does the branching happen

i wanna understand it

John Rennie

Oct 15, 2019 09:42

Do you know how the Fibonacci sequence works?

Aladdin

yes

like 1,1,3,5

the next number is sum of 1,1 and 3

something like this

John Rennie

Yes, the nth term F(n) is given by F(n) = F(n-1) + F(n-2)

Aladdin

ok

John Rennie

i.e. each term is the sum of the two preceding terms.

So coding this is really easy since F(n) = F(n-1) + F(n-2) is basically yhe definition of the function.

All you need to add is code to return 1 if n=1 or n=2 i.e. the first two numbers in the sequence are both equal to 1.

Aladdin

@JohnRennie When you run the program

first it shows fun(6)-fun(5)-fun(4)-fun(3)

something like this

then it traces back

why does it trace back

John Rennie

Oct 15, 2019 09:50

The bit of the function that does the work is return fun(n - 1) + fun(n - 2)

so when you call fun(6) it calls fun(n-1) i.e. fun(5). Then that calls fun(4) and that calls fun(3) and so on.

CodeClub

Participants